구현

KMP 검색과 트라이를 Python으로 구현해 설명하고, 같은 KMP 핵심 루틴을 C++, Java, TypeScript로 옮깁니다.

Python: KMP

def prefix_function(p: str) -> list[int]:
    pi = [0] * len(p)                    # pi[i]: p[0..i]의 가장 긴 경계 길이
    k = 0                                # 직전 위치의 경계 길이
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:    # 늘릴 수 없으면 더 짧은 경계로
            k = pi[k - 1]
        if p[i] == p[k]:                 # 한 글자 늘릴 수 있으면 늘린다
            k += 1
        pi[i] = k
    return pi


def kmp_search(text: str, pattern: str) -> list[int]:
    m = len(pattern)
    if m == 0:
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    hits, k = [], 0                         # k: 지금까지 일치한 길이
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == m:
            hits.append(i - m + 1)
            k = pi[k - 1]                   # 겹치는 출현도 찾도록 이어 간다
    return hits


assert prefix_function("ababaca") == [0, 0, 1, 2, 3, 0, 1]
assert kmp_search("abababcabab", "abab") == [0, 2, 7]
assert kmp_search("aaaa", "aa") == [0, 1, 2]

• while은 실패할 때 k를 줄이고, if는 일치할 때 한 칸 늘립니다. 두 함수의 뼈대가 같습니다.
• 빈 패턴은 str.find처럼 모든 위치에서 일치한다고 정했습니다. 이 처리가 없으면 pattern[0]에서 인덱스 오류가 납니다.
• i - m + 1은 패턴이 끝난 위치 i에서 거꾸로 계산한 시작 위치입니다.

Python: 트라이와 자동 완성

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _walk(self, prefix: str) -> TrieNode | None:
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def complete(self, prefix: str, limit: int = 10) -> list[str]:
        start = self._walk(prefix)
        if start is None:
            return []
        out: list[str] = []
        stack = [(start, prefix)]
        while stack and len(out) < limit:
            node, word = stack.pop()
            if node.is_end:
                out.append(word)
            for ch in sorted(node.children, reverse=True):
                stack.append((node.children[ch], word + ch))
        return out


t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
assert t.complete("ca") == ["car", "cart", "cat"]

• 자식은 dict로 두어 어떤 알파벳에도 쓸 수 있습니다. 소문자만 쓴다면 길이 26 배열이 더 빠릅니다.
• is_end가 없으면 접두사일 뿐인 ca도 단어로 나옵니다.
• complete는 재귀 대신 명시적 스택을 씁니다. 자식을 역순으로 넣으므로 사전순으로 꺼내지고, limit개를 모으면 멈춥니다.

C++

#include <string>
#include <vector>

std::vector<int> prefixFunction(const std::string& p) {
    std::vector<int> pi(p.size(), 0);
    int k = 0;
    for (size_t i = 1; i < p.size(); ++i) {
        while (k > 0 && p[i] != p[k]) k = pi[k - 1];
        if (p[i] == p[k]) ++k;
        pi[i] = k;
    }
    return pi;
}

std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> hits;
    const int m = static_cast<int>(pattern.size());
    if (m == 0) return hits;
    const std::vector<int> pi = prefixFunction(pattern);
    int k = 0;
    for (size_t i = 0; i < text.size(); ++i) {
        while (k > 0 && text[i] != pattern[k]) k = pi[k - 1];
        if (text[i] == pattern[k]) ++k;
        if (k == m) {
            hits.push_back(static_cast<int>(i) - m + 1);
            k = pi[k - 1];
        }
    }
    return hits;
}

std::string은 바이트 단위이므로 UTF-8 텍스트에서는 바이트 위치를 돌려줍니다. 빈 패턴은 빈 결과로 단순화했습니다.

Java

import java.util.ArrayList;
import java.util.List;

public final class Kmp {
    static int[] prefixFunction(String p) {
        int[] pi = new int[p.length()];
        int k = 0;
        for (int i = 1; i < p.length(); i++) {
            while (k > 0 && p.charAt(i) != p.charAt(k)) k = pi[k - 1];
            if (p.charAt(i) == p.charAt(k)) k++;
            pi[i] = k;
        }
        return pi;
    }

    static List<Integer> search(String text, String pattern) {
        List<Integer> hits = new ArrayList<>();
        int m = pattern.length();
        if (m == 0) return hits;
        int[] pi = prefixFunction(pattern);
        int k = 0;
        for (int i = 0; i < text.length(); i++) {
            while (k > 0 && text.charAt(i) != pattern.charAt(k)) k = pi[k - 1];
            if (text.charAt(i) == pattern.charAt(k)) k++;
            if (k == m) {
                hits.add(i - m + 1);
                k = pi[k - 1];
            }
        }
        return hits;
    }
}

Java의 charAt은 UTF-16 코드 단위를 돌려줍니다. 텍스트와 패턴을 같은 방식으로 나누므로 일치 판정은 정확하지만, 위치는 코드 단위 기준입니다.

TypeScript

export function prefixFunction(p: string): number[] {
  const pi = new Array<number>(p.length).fill(0);
  let k = 0;
  for (let i = 1; i < p.length; i++) {
    while (k > 0 && p[i] !== p[k]) k = pi[k - 1];
    if (p[i] === p[k]) k++;
    pi[i] = k;
  }
  return pi;
}

export function kmpSearch(text: string, pattern: string): number[] {
  const hits: number[] = [];
  const m = pattern.length;
  if (m === 0) return hits;
  const pi = prefixFunction(pattern);
  let k = 0;
  for (let i = 0; i < text.length; i++) {
    while (k > 0 && text[i] !== pattern[k]) k = pi[k - 1];
    if (text[i] === pattern[k]) k++;
    if (k === m) {
      hits.push(i - m + 1);
      k = pi[k - 1];
    }
  }
  return hits;
}

정리

• KMP의 두 함수는 "실패하면 줄이고, 일치하면 늘린다"는 같은 뼈대를 씁니다.
• 트라이는 노드마다 자식 맵과 is_end 표시를 두며, 자동 완성은 접두사 노드에서 아래를 훑습니다.
• 위치 단위는 C++이 바이트, Java와 TypeScript가 UTF-16 코드 단위, Python이 코드 포인트입니다.