동작 원리

이 장에서는 작은 예제를 손으로 따라가며 KMP, Rabin-Karp, 트라이, Z 알고리즘이 어떻게 움직이는지 봅니다. 표의 값을 직접 계산해 보면 코드가 훨씬 쉽게 읽힙니다.

KMP 1단계: 접두사 함수(실패 표)

접두사 함수 pi[i]는 "패턴의 앞 i + 1글자(p[0..i])에서 가장 긴 경계의 길이"입니다. 실패 함수 또는 실패 표라고도 부릅니다. 패턴 ababaca로 계산해 봅니다.

계산은 왼쪽에서 오른쪽으로 진행하며, 변수 k에 "직전 위치의 경계 길이"를 들고 다닙니다.

1. i = 1: p[1] = b와 p[0] = a가 다르고 k = 0이므로 pi[1] = 0입니다.
2. i = 2: p[2] = a가 p[0]과 같으므로 k = 1, pi[2] = 1입니다.
3. i = 3, 4: 계속 일치해서 k가 2, 3으로 늘어납니다.
4. i = 5: p[5] = c가 p[3] = b와 다릅니다. 그러면 k = pi[k - 1] = pi[2] = 1로 줄여 더 짧은 경계를 시도합니다. p[1] = b와도 다르므로 다시 k = pi[0] = 0이 되고, p[0] = a와도 달라 pi[5] = 0입니다.
5. i = 6: p[6] = a가 p[0]과 같아 pi[6] = 1입니다.

핵심은 4단계입니다. 실패했을 때 처음부터 다시 비교하지 않고 "지금 경계 안의 더 짧은 경계"로 바로 넘어갑니다. 경계의 경계도 경계이기 때문에 이렇게 해도 놓치는 후보가 없습니다.

def prefix_function(p: str) -> list[int]:
    pi = [0] * len(p)
    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


print(prefix_function("ababaca"))  # [0, 0, 1, 2, 3, 0, 1]

KMP 2단계: 텍스트 훑기

검색도 같은 방식입니다. k는 "지금까지 일치한 패턴 길이"이고, 텍스트 포인터 i는 절대 뒤로 가지 않습니다. 텍스트 abababcabab에서 패턴 abab(pi = [0, 0, 1, 2])를 찾습니다.

발견 직후 k를 0이 아니라 pi[m - 1]로 두기 때문에 위치 0과 2처럼 겹치는 출현도 찾습니다.

Rabin-Karp: 굴러가는 해시

Rabin-Karp는 길이 m인 창(window)의 해시값을 패턴의 해시값과 비교합니다. 창을 한 칸 밀 때 해시를 처음부터 다시 계산하지 않고 맨 앞 글자를 빼고 새 글자를 더해 O(1)에 갱신합니다.

h(s) = (s[0]·B^(m-1) + s[1]·B^(m-2) + ... + s[m-1]) mod M
다음 창: h' = ((h - s[i]·B^(m-1))·B + s[i+m]) mod M

이해를 돕기 위해 숫자 문자열에 B = 10, M = 11을 써 봅니다. 텍스트는 31415926, 패턴은 1592이며 패턴의 해시는 1592 mod 11 = 8입니다.

마지막 줄처럼 해시가 같아도 문자열이 다를 수 있습니다. 그래서 해시가 같으면 반드시 실제 글자를 비교해 확인합니다. 실전에서는 M을 10**9 + 7처럼 큰 소수로, B를 무작위로 골라 충돌을 드물게 만듭니다.

def window_hashes(text: str, m: int, base: int = 10, mod: int = 11) -> list[int]:
    high = pow(base, m - 1, mod)
    h = 0
    for ch in text[:m]:
        h = (h * base + int(ch)) % mod
    out = [h]
    for i in range(len(text) - m):
        h = ((h - int(text[i]) * high) * base + int(text[i + m])) % mod
        out.append(h)
    return out


print(window_hashes("31415926", 4))  # [6, 7, 1, 8, 8]

트라이: 접두사를 공유하는 나무

트라이는 단어의 글자를 따라 내려가는 나무입니다. car, cart, cat, dog를 넣으면 공통 접두사 ca를 한 경로로 공유합니다. *는 단어가 끝나는 노드입니다.

(root)
 ├─ c ─ a ─ r* ─ t*
 │        └─ t*
 └─ d ─ o ─ g*

접두사 ca로 자동 완성하려면 c, a를 따라 내려간 노드에서 아래쪽의 단어 끝 표시를 모두 모읍니다. 결과는 car, cart, cat입니다. 내려가는 비용은 접두사 길이에만 비례하고 사전 크기와는 무관합니다.

Z 알고리즘 짧게 보기

Z 배열의 z[i]는 "s[i:]와 s 전체의 가장 긴 공통 접두사 길이"입니다. aabxaab의 Z 배열은 [7, 1, 0, 0, 3, 1, 0]입니다(관례상 z[0]은 길이 또는 0). 패턴 검색에는 패턴 + "$" + 텍스트의 Z 배열을 구하고 값이 m인 위치를 찾으면 됩니다. 구분자 $는 두 문자열에 나오지 않는 글자여야 합니다. 이미 구한 [l, r) 구간(Z 상자)을 재사용해 전체를 O(n + m)에 계산합니다.

정리

• 접두사 함수는 실패 시 "경계의 경계"로 이동해 텍스트 포인터를 되돌리지 않습니다.
• KMP는 발견 후 k = pi[m - 1]로 두어 겹치는 출현도 찾습니다.
• Rabin-Karp는 창의 해시를 O(1)에 갱신하고, 해시가 같으면 글자를 비교해 거짓 양성을 걸러 냅니다.
• 트라이는 공통 접두사를 공유하며, Z 배열은 KMP와 같은 일을 다른 관점으로 합니다.