복잡도

이 장에서는 텍스트 길이 n, 패턴 길이 m, 알파벳 크기 σ를 기준으로 각 알고리즘의 시간과 공간을 분석합니다. 문자열 알고리즘은 평균과 최악의 차이가 큰 경우가 많으므로 두 경우를 함께 봅니다.

순진한 매칭

시작 위치가 n - m + 1개이고 위치마다 최대 m번 비교하므로 최악은 O(n·m)입니다. 텍스트 aaaa...a와 패턴 aa...ab가 대표적인 최악 입력입니다. 반대로 알파벳이 크고 텍스트가 무작위에 가까우면 대부분 첫 글자나 두 번째 글자에서 실패하므로 평균은 O(n)에 가깝습니다. 추가 메모리는 O(1)입니다.

KMP가 선형인 이유

KMP의 while 루프는 언뜻 보면 중첩 루프처럼 보이지만 전체 비용은 O(n + m)입니다. 상각(amortized) 분석으로 보이면 다음과 같습니다.

1. k는 텍스트 한 글자마다 최대 1만큼 늘어나므로 전체 증가량은 많아야 n입니다.
2. while 루프는 돌 때마다 k를 최소 1만큼 줄입니다. k는 0 아래로 내려가지 않습니다.
3. 따라서 while이 도는 총 횟수는 전체 증가량, 즉 n을 넘을 수 없습니다.

접두사 함수 계산에도 같은 논리가 적용되어 O(m)입니다. 공간은 pi 배열 O(m)이며, 텍스트를 한 번만 앞으로 읽으므로 스트림에도 그대로 쓸 수 있습니다.

비교 횟수를 직접 세어 보면 차이가 잘 드러납니다.

def naive_comparisons(text: str, pattern: str) -> int:
    count = 0
    for s in range(len(text) - len(pattern) + 1):
        for j in range(len(pattern)):
            count += 1
            if text[s + j] != pattern[j]:
                break
    return count


def kmp_comparisons(text: str, pattern: str) -> int:
    pi = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k > 0 and pattern[i] != pattern[k]:
            k = pi[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        pi[i] = k
    count, k = 0, 0
    for ch in text:
        while True:
            count += 1
            if ch == pattern[k]:
                k += 1
                break
            if k == 0:
                break
            k = pi[k - 1]
        if k == len(pattern):
            k = pi[k - 1]
    return count


text, pattern = "a" * 10_000, "a" * 99 + "b"
print(naive_comparisons(text, pattern))  # 990100
print(kmp_comparisons(text, pattern))    # 19901

같은 입력에서 순진한 방법은 약 99만 번, KMP는 약 2만 번 비교합니다. KMP의 비교 횟수는 항상 2n 이하입니다.

Rabin-Karp

해시를 굴리는 비용은 창마다 O(1)이므로 해시 계산 전체는 O(n + m)입니다. 해시가 같을 때마다 O(m) 확인을 하므로 실제 출현이 occ번이고 충돌이 드물다면 기대 시간은 O(n + m + occ·m)입니다. 모듈러 M이 작거나 입력이 충돌을 노리고 만들어졌다면 거의 모든 창에서 확인이 일어나 최악 O(n·m)이 됩니다. 공간은 O(1)입니다.

Rabin-Karp가 빛나는 곳은 길이가 같은 패턴 여러 개를 찾을 때입니다. 패턴의 해시를 집합에 넣어 두면 창마다 집합 조회 한 번으로 끝나므로, 패턴 k개를 찾는 데 O(n + k·m) 기대 시간이 듭니다.

def multi_rabin_karp(text: str, patterns: set[str], base: int = 911382323, mod: int = (1 << 61) - 1) -> list[tuple[int, str]]:
    m = len(next(iter(patterns)))
    assert all(len(p) == m for p in patterns)
    def h(s: str) -> int:
        v = 0
        for ch in s:
            v = (v * base + ord(ch)) % mod
        return v
    wanted = {h(p) for p in patterns}
    high = pow(base, m - 1, mod)
    out, cur = [], h(text[:m])
    for i in range(len(text) - m + 1):
        if cur in wanted and text[i:i + m] in patterns:
            out.append((i, text[i:i + m]))
        if i + m < len(text):
            cur = ((cur - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return out


print(multi_rabin_karp("the cat sat on the mat", {"cat", "mat", "dog"}))
# [(4, 'cat'), (19, 'mat')]

트라이

길이 L인 단어의 삽입, 검색, 접두사 이동은 모두 O(L)이며 사전에 단어가 몇 개 있는지와 무관합니다. 자동 완성은 접두사까지 내려가는 O(L)에 결과를 모으며 방문하는 노드 수가 더해집니다. 공간은 노드 수가 최대 전체 글자 수 N이므로, 자식을 길이 σ 배열로 두면 O(N·σ), 해시 맵으로 두면 O(N)입니다. 단어가 공통 접두사를 적게 공유하면 노드가 많아지므로, 한 갈래로만 이어지는 노드를 합친 압축 트라이(radix tree)를 씁니다.

정렬된 리스트와 이진 탐색으로도 접두사 검색을 할 수 있습니다. 단어 목록이 거의 바뀌지 않는다면 메모리 면에서 더 유리합니다.

import bisect

words = sorted(["car", "cart", "cat", "dog", "dot"])
lo = bisect.bisect_left(words, "ca")
hi = bisect.bisect_left(words, "cb")   # "ca" 다음 접두사
print(words[lo:hi])  # ['car', 'cart', 'cat']

비교 표

정리

• KMP와 Z는 최악에도 선형이며, 증가량으로 감소량을 묶는 상각 분석이 핵심입니다.
• Rabin-Karp는 기대 선형이지만 충돌에 따라 최악 O(n·m)이 될 수 있습니다.
• 트라이 연산은 단어 길이에만 비례하지만 메모리 비용이 크므로 압축 트라이나 정렬 리스트도 함께 고려합니다.