문자열 검색에서 단순한 방법은 텍스트의 모든 위치에 패턴을 맞춰 보고, 한 글자가 다르면 패턴을 한 칸 옮기는 것입니다. 패턴이 aaaaab처럼 반복되는 문자를 많이 포함하면 이미 비교한 텍스트를 다시 읽는 일이 반복됩니다. KMP(Knuth–Morris–Pratt)는 이 반복을 없애기 위해 패턴 자체에서 어디까지 같은 접두를 다시 살릴 수 있는지를 기록합니다. 핵심 자료구조가 접두 함수(prefix function) π이고, 검색 중 현재 상태는 “패턴의 앞에서부터 몇 글자까지 텍스트의 끝과 일치했는가”입니다.
이 노트에서 말하는 문자열의 문자 단위는 구현이 선택한 입력 단위입니다. C++의 string 예처럼 바이트를 순회할 수도 있고, 코드 포인트를 미리 배열로 만들 수도 있습니다. UTF-8 바이트와 사람이 인식하는 문자를 혼동하면 알고리즘의 접두 길이와 사용자 화면의 위치가 달라집니다.
접두 함수의 의미
길이 n인 문자열 s에 대해 π[i]는 s[0..i]의 가장 긴 proper prefix이면서 suffix인 길이입니다. proper prefix는 전체 문자열과 같지 않은 접두이므로 π[0] = 0입니다. 예를 들어 s = ababa라면 마지막 위치에서 접두 aba와 접미 aba가 겹치므로 π[4] = 3입니다. ababa 전체는 proper prefix가 아니므로 길이 5를 답으로 쓰지 않습니다.
이 값은 단순한 일치 길이가 아니라 다음 후보를 가리키는 인덱스입니다. 길이 j인 border가 실패하면 그 border의 가장 긴 proper border는 π[j-1]입니다. 따라서 긴 후보를 매번 앞에서부터 재검사하지 않고 j ← π[j-1]로 점프합니다. border들의 사슬은 j, π[j-1], 다시 그 값에 해당하는 접두의 border로 이어집니다.
그림을 글로 읽기
- 현재 상태 4: 접두 abab와 일치
- π[3] = 2: 후보 ab
- π[1] = 0: 더 짧은 후보 없음
- 현재 상태 4 → π[3] = 2: 불일치 시 fallback
- π[3] = 2 → π[1] = 0: 다시 실패하면 π[1]
접두 함수 계산
i를 1부터 늘리며 j = π[i-1]에서 시작합니다. s[i]와 s[j]가 같으면 현재 border 뒤에 한 글자를 붙여 j+1이 됩니다. 다르면 j > 0인 동안 j = π[j-1]로 짧은 border를 시험합니다. j=0에서 계속 다르면 π[i]=0입니다. 구현의 핵심은 불일치 루프에서 i를 뒤로 보내지 않는다는 점입니다.
prefix_function(s):
pi = [0] * len(s)
for i in 1 .. len(s)-1:
j = pi[i-1]
while j > 0 and s[i] != s[j]:
j = pi[j-1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
예를 들어 ababaca의 π를 계산하면 [0, 0, 1, 2, 3, 0, 1]입니다. i=5의 문자는 c이고 직전 상태는 j=3입니다. s[5] != s[3]이므로 j=π[2]=1로 내려갑니다. 다시 s[5] != s[1]이므로 j=π[0]=0이 되고, c != s[0]이어서 0이 됩니다. 이 과정에서 aba나 a를 텍스트와 다시 비교하지 않습니다.
왜 이 계산이 선형인가도 상태 변화로 설명할 수 있습니다. i가 한 칸 진행할 때 j는 최대 한 칸 증가합니다. 반대로 감소는 여러 칸일 수 있지만, 이전에 증가한 양을 누적해서 소모합니다. 모든 i에 대해 j가 무한히 반복해서 감소할 수 없으므로 비교·fallback 총량은 O(n)입니다. 참조 구현은 이를 “이미 계산된 prefix property를 π[j-1]로 재사용한다”는 방식으로 제시합니다.
검색 상태 전이
패턴 p의 접두 함수 π를 먼저 구한 뒤 텍스트를 왼쪽에서 오른쪽으로 한 번 읽습니다. 현재 상태 j는 텍스트의 지금까지 읽은 부분 끝이 패턴의 p[0..j-1]와 일치하는 길이입니다. 새 문자 c가 p[j]와 같으면 j++합니다. 다르면 j > 0인 동안 j = π[j-1]로 내려간 뒤 같은 c를 새 상태에서 비교합니다.
j == m, 즉 패턴 길이 m에 도달하면 끝 위치는 현재 텍스트 인덱스 i이고 시작 위치는 i-m+1입니다. 겹치는 출현을 허용하려면 보고한 뒤 j = π[m-1]로 바꿉니다. 이를 0으로 만들면 ababa 안의 aba 같은 다음 겹침을 놓칩니다. 빈 패턴을 허용할지, 허용한다면 위치를 어떻게 정의할지는 알고리즘 바깥의 API 계약으로 고정해야 합니다.
패턴 aba, 텍스트 ababa를 추적하면 다음과 같습니다.
| 텍스트 위치 | 문자 | 처리 전 j |
처리 후 j |
보고 |
|---|---|---|---|---|
| 0 | a | 0 | 1 | 없음 |
| 1 | b | 1 | 2 | 없음 |
| 2 | a | 2 | 3 | 시작 0 |
| 3 | b | 1 | 2 | 없음 |
| 4 | a | 2 | 3 | 시작 2 |
세 번째 문자에서 완전 일치 후 π[2]=1로 돌아갔기 때문에 네 번째 이후의 aba를 이어갈 수 있습니다. 텍스트 인덱스와 패턴 인덱스를 혼합해 i-j를 잘못 계산하는 것이 흔한 오프바이원 원인입니다.
결합 문자열과 구분자
또 다른 설명 방식은 p + sep + t를 하나의 문자열로 만들고 접두 함수를 계산하는 것입니다. sep는 패턴과 텍스트 어디에도 나타나지 않는 값이어야 합니다. 텍스트 부분의 어떤 위치에서 π[i] == |p|이면 그 위치에서 패턴 전체가 끝난 것입니다. 결합 문자열의 텍스트 시작 오프셋이 |p|+1이고, 끝 위치가 i이며, 매치 길이가 |p|이므로 텍스트 시작은 i - 2|p|가 됩니다. 이 위치 변환은 예제 하나로 확인하지 말고 인덱스 식을 적어 검증해야 합니다.
구분자는 보통 스트리밍 KMP 자체에 필요한 것이 아닙니다. 스트리밍 방식은 패턴의 π, 현재 j, 텍스트 위치만 가지고 새 입력을 처리하므로 경계 토큰을 비교하지 않습니다. 반대로 결합 방식의 π[i] == m 판정은 sep가 패턴과 텍스트에 모두 없다는 전제에 의존합니다. 예를 들어 p=a, sep=#, t=a#a이면 결합 문자열은 a#a#a이고 텍스트의 두 번째 a에서 접두 함수가 3까지 자랄 수 있습니다. == m을 고집하면 실제로는 >= m인 출현을 놓치므로, 패턴 안에는 sep가 없고 text에는 sep가 없다는 계약을 강제해야 합니다. 그 계약을 만들 수 없다면 결합을 거부하고 직접 streaming KMP를 사용해야 합니다.
스트리밍과 메모리 경계
패턴이 고정이고 텍스트가 소켓 청크로 들어오면 청크마다 상태를 0으로 초기화하지 않습니다. j와 텍스트의 누적 위치를 다음 청크로 넘기고, 첫 문자를 기존 상태에서 바로 처리합니다. 패턴 길이가 4이고 청크 끝에서 j=3이었다면 다음 청크의 문자가 패턴 네 번째 문자와 일치하는 순간 매치를 보고한 뒤 π[3]으로 fallback합니다.
저장할 값은 패턴 자체, π, 현재 j, 누적 텍스트 위치입니다. 전체 텍스트를 저장할 필요는 없습니다. 참조 설명도 패턴과 구분자 및 prefix 값만 보관하고 텍스트는 한 문자씩 읽는 O(n+m) 시간, O(m) 추가 메모리 구성을 제시합니다. 단, 바이트 오프셋과 코드 포인트 오프셋 중 무엇을 외부에 반환할지에 따라 위치 카운터의 단위는 달라집니다.
접두 함수 자체도 입력을 한 글자씩 받는 online 계산이 가능합니다. 다만 일반 구현은 이미 본 패턴 문자와 π 배열을 사용하므로 “상태 하나만 저장”이라는 뜻은 아닙니다. 패턴의 최대 border 길이를 알고 저장을 제한하는 최적화와, 검색 중 패턴 전체를 보관해야 하는 공개 API의 편의성은 구분해야 합니다.
반복 주기와 border 활용
문자열 길이를 n이라 하고 마지막 접두 함수 값을 π[n-1]이라 하면 k = n - π[n-1]를 최소 반복 블록 후보로 볼 수 있습니다. n % k == 0이면 길이 k의 블록이 전체를 반복하고, 아니면 이 후보는 전체 반복 주기가 아닙니다. ababab에서는 π[5]=4, k=2, 6 % 2 = 0이므로 ab가 세 번 반복됩니다. 반대로 ababa도 긴 border가 있지만 k=2, 5 % 2 != 0이므로 ab 반복으로 판정하면 안 됩니다.
이 조건에서 border는 “접두와 접미가 겹친다”는 사실만 제공하고, 나눗셈 조건이 반복 블록이 전체 길이를 덮는지를 확인합니다. n을 k로 나누지 않는 문자열을 단지 k라는 후보가 있다는 이유로 압축하면 접미 겹침과 전체 주기를 혼동하게 됩니다.
선택·검증·한계
단일 패턴을 긴 텍스트에서 반복 검색하거나 입력이 스트리밍이면 KMP가 적합합니다. 여러 패턴을 동시에 찾아야 하면 패턴마다 KMP를 돌리는 대신 trie와 실패 링크를 결합한 Aho-Corasick이 구조적으로 맞습니다. 정적 문자열의 여러 종류 질의, 부분 문자열 비교, 해시 기반 필터가 필요하면 다른 선택이 나을 수 있습니다. KMP의 선형 시간은 문자 비교 모델과 고정 패턴 전제를 두며, 결과를 모두 출력하는 시간까지 없애 주지는 않습니다.
검증은 π[0]=0, 경계가 전혀 없는 문자열, 전부 같은 문자, 긴 border 뒤 불일치, 겹치는 매치, 청크 경계 매치를 포함해야 합니다. 작은 입력에서는 설명용 계산으로 naive 검색 결과와 KMP 결과의 시작 위치를 대조할 수 있지만, 여기의 코드는 실행한 결과가 아니라 알고리즘 설명용입니다. 결합 문자열 테스트에는 구분자가 입력에 존재하는 경우를 별도 실패 케이스로 둡니다.
참고한 cp-algorithms의 “Prefix function. Knuth–Morris–Pratt algorithm” 문서는 2023-08-20 갱신본으로, 접두 함수 정의, j = π[j-1] fallback, online 계산, s + # + t 검색 및 O(n+m) 시간·O(n) 저장을 설명합니다. 구현 언어의 문자열 단위나 빈 패턴 정책은 그 문서가 정하지 않으므로 서비스 계약에서 별도로 결정해야 합니다.
참고 경로
위 링크는 개념별 참고 경로이며, 본문에서 명시한 확인 범위와 미확인 구현 조건을 함께 적용합니다.