coding-test/
└── 16-advanced-strings/
    ├── 01-kmp-search/
    │   ├── solution.js            (+)
    │   └── solution.test.js       (+)
    ├── 02-trie/
    │   ├── solution.js            (+)
    │   └── solution.test.js        (+)
    └── 03-longest-palindrome/
        ├── solution.js             (+)
        └── solution.test.js        (+)

// coding-test/16-advanced-strings/01-kmp-search/solution.js
// 시간복잡도: O(n + m) — 실패 테이블 생성 O(m) + 텍스트 순회 O(n)
// 공간복잡도: O(m) — 패턴 길이만큼의 실패 테이블을 저장한다
function buildFailureTable(pattern) {
  const table = new Array(pattern.length).fill(0);
  let prefixLength = 0;
  let i = 1;
 
  while (i < pattern.length) {
    if (pattern[i] === pattern[prefixLength]) {
      prefixLength += 1;
      table[i] = prefixLength;
      i += 1;
    } else if (prefixLength > 0) {
      prefixLength = table[prefixLength - 1];
    } else {
      table[i] = 0;
      i += 1;
    }
  }
  return table;
}
 
export function solution(text, pattern) {
  if (pattern.length === 0) return 0;
 
  const table = buildFailureTable(pattern);
  let textIndex = 0;
  let patternIndex = 0;
 
  while (textIndex < text.length) {
    if (text[textIndex] === pattern[patternIndex]) {
      textIndex += 1;
      patternIndex += 1;
      if (patternIndex === pattern.length) {
        return textIndex - patternIndex;
      }
    } else if (patternIndex > 0) {
      patternIndex = table[patternIndex - 1];
    } else {
      textIndex += 1;
    }
  }
  return -1;
}

// coding-test/16-advanced-strings/01-kmp-search/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
 
test('반복되는 부분 문자열이 있어도 정확한 위치를 찾는다', () => {
  assert.strictEqual(solution('ababcabcabababd', 'ababd'), 10);
});
 
test('일반적인 문자열에서 패턴 위치를 찾는다', () => {
  assert.strictEqual(solution('hello world', 'world'), 6);
});
 
test('패턴이 없으면 -1을 반환한다', () => {
  assert.strictEqual(solution('abc', 'xyz'), -1);
});
 
test('패턴이 빈 문자열이면 0을 반환한다', () => {
  assert.strictEqual(solution('abc', ''), 0);
});

node --test coding-test/16-advanced-strings/01-kmp-search/solution.test.js

// coding-test/16-advanced-strings/02-trie/solution.js
// 시간복잡도: O(L) — insert·search·startsWith 모두 단어 길이 L에 비례한다
// 공간복잡도: O(전체 단어 길이 합) — 공통 접두사는 노드를 공유해 저장한다
class TrieNode {
  children = new Map();
  isEndOfWord = false;
}
 
export class Trie {
  #root = new TrieNode();
 
  insert(word) {
    let node = this.#root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.isEndOfWord = true;
  }
 
  search(word) {
    const node = this.#findNode(word);
    return node !== null && node.isEndOfWord;
  }
 
  startsWith(prefix) {
    return this.#findNode(prefix) !== null;
  }
 
  #findNode(prefix) {
    let node = this.#root;
    for (const char of prefix) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char);
    }
    return node;
  }
}

// coding-test/16-advanced-strings/02-trie/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { Trie } from './solution.js';
 
function makeTrie() {
  const trie = new Trie();
  for (const word of ['apple', 'app', 'application']) {
    trie.insert(word);
  }
  return trie;
}
 
test('저장한 단어는 search에서 true를 반환한다', () => {
  assert.strictEqual(makeTrie().search('app'), true);
});
 
test('저장하지 않은 문자열은 search에서 false를 반환한다', () => {
  assert.strictEqual(makeTrie().search('appl'), false);
});
 
test('저장된 단어들의 접두사는 startsWith에서 true를 반환한다', () => {
  assert.strictEqual(makeTrie().startsWith('appl'), true);
});
 
test('어떤 단어의 접두사도 아니면 startsWith에서 false를 반환한다', () => {
  assert.strictEqual(makeTrie().startsWith('banana'), false);
});

node --test coding-test/16-advanced-strings/02-trie/solution.test.js

// coding-test/16-advanced-strings/03-longest-palindrome/solution.js
// 시간복잡도: O(n^2) — 중심 후보 2n-1개에서 각각 최대 n번 확장한다
// 공간복잡도: O(1) — 시작 위치와 최대 길이만 변수로 유지한다
export function solution(text) {
  if (text.length === 0) return '';
 
  let start = 0;
  let maxLength = 1;
 
  function expandAroundCenter(left, right) {
    while (left >= 0 && right < text.length && text[left] === text[right]) {
      const currentLength = right - left + 1;
      if (currentLength > maxLength) {
        maxLength = currentLength;
        start = left;
      }
      left -= 1;
      right += 1;
    }
  }
 
  for (let center = 0; center < text.length; center++) {
    expandAroundCenter(center, center);
    expandAroundCenter(center, center + 1);
  }
  return text.slice(start, start + maxLength);
}

// coding-test/16-advanced-strings/03-longest-palindrome/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
 
test('홀수 길이 팰린드롬을 찾는다', () => {
  const result = solution('babad');
  assert.ok(result === 'bab' || result === 'aba');
});
 
test('짝수 길이 팰린드롬을 찾는다', () => {
  assert.strictEqual(solution('cbbd'), 'bb');
});
 
test('글자 하나는 그대로 반환한다', () => {
  assert.strictEqual(solution('a'), 'a');
});
 
test('빈 문자열이면 빈 문자열을 반환한다', () => {
  assert.strictEqual(solution(''), '');
});

node --test coding-test/16-advanced-strings/03-longest-palindrome/solution.test.js