KMP 문자열 검색 쉽게 이해하기: 동작 원리, 코드, 시간 복잡도

KMP가 해결하는 문제

문자열 검색은 짧은 패턴이 긴 텍스트의 어디에 나타나는지 묻습니다. 단순한 방법은 모든 시작 위치를 시도하며 문자를 하나씩 비교합니다. 일반적인 텍스트에서는 빠르지만 반복적인 입력에서는 느립니다. aaaaaaaaaa에서 aaaab를 찾으면 각 위치에서 패턴 거의 전체를 비교하게 되어 O(n × m) 시간이 걸립니다.

KMP는 불일치가 일어난 뒤 텍스트 문자를 다시 읽지 않습니다. 도널드 크누스(Donald Knuth), 제임스 H. 모리스(James H. Morris), 본 프랫(Vaughan Pratt)이 1977년 "Fast Pattern Matching in Strings"에서 발표했습니다.

핵심 아이디어

패턴 ABABC를 찾고 있고 ABAB까지 일치했는데 다음 텍스트 문자가 C가 아니라고 합시다. 방금 일치한 ABAB는 AB로 끝나는데, 이는 패턴의 시작과도 같습니다. 따라서 다음 시도는 이미 2글자가 일치한 상태로 시작한다는 것을 알고, 처음부터 다시 하는 대신 패턴의 2번 위치부터 비교를 이어 갈 수 있습니다.

접두사 함수는 이 숫자들을 저장합니다. pi[i]는 pattern[0..i]의 진접두사 중 접미사이기도 한 가장 긴 것의 길이입니다(진(proper)이란 문자열 전체가 아니라는 뜻).

예를 들어 pi[4] = 3인 이유는 ABABA가 ABA로 시작하고 끝나기 때문입니다. pi[5] = 0인 이유는 ABABAC의 어떤 접두사도 C로 끝나지 않기 때문입니다.

단계별 예제

텍스트 ABABABC에서 패턴 ABABC(접두사 함수 0, 0, 1, 2, 0)를 검색합니다. 변수 k는 현재 일치한 패턴 문자의 수입니다.

텍스트 포인터는 7번 앞으로만 움직이고 한 번도 뒤로 가지 않았습니다. 단순한 방법이라면 1번 위치에서 다시 시작해 일부 문자를 다시 비교했을 것입니다.

파이썬 구현

def prefix_function(p):
    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]          # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    """Return the start index of every occurrence (overlaps included)."""
    if not pattern:
        return []
    pi, k, hits = prefix_function(pattern), 0, []
    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 == len(pattern):
            hits.append(i - k + 1)
            k = pi[k - 1]          # keep going to find overlapping matches
    return hits

print(prefix_function("ABABACA"))      # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("ABABABC", "ABABC"))  # [2]
print(kmp_search("AAAAA", "AA"))       # [0, 1, 2, 3]

시간 복잡도와 공간 복잡도

단순한 알고리즘은 최악의 경우 O(n × m)이지만 자연어 텍스트에서는 O(n)에 가까운 경우가 많으므로, KMP의 장점은 주로 반복적인 데이터에서 드러납니다.

변형과 흔한 실수

• 폴백에서의 off-by-one: 불일치 이후에는 k = pi[k]가 아니라 k = pi[k - 1]로 설정합니다. pi는 마지막으로 일치한 위치로 인덱싱됩니다.
• 폴백에 while 대신 if를 사용함: 문자가 일치하기 전에 폴백이 연속으로 여러 번 필요할 수 있습니다.
• 완전 일치 후 k를 재설정하는 것을 잊음: 겹치는 일치를 찾으려면 k = pi[k - 1]로, 겹치지 않는 일치만 찾으려면 k = 0으로 설정합니다.
• 이어 붙이기 기법: 둘 어디에도 나오지 않는 구분자를 사용해 pattern + separator + text의 접두사 함수를 계산합니다. 값이 m인 모든 위치가 일치의 끝입니다.
• Z 알고리즘은 매우 비슷한 배열을 계산하며 마찬가지로 O(n + m)에 검색합니다.

언제 쓰는지와 실제 활용

• 코딩 인터뷰 문제: strStr() 구현, 가장 짧은 팰린드롬(s + "#" + reversed(s)의 접두사 함수), 반복되는 부분 문자열 패턴, 문자열의 최소 주기(m - pi[m - 1]).
• 실제 사례: 최악의 경우에도 선형 시간이 중요한 DNA 서열이나 네트워크 패킷 스트림 검색.