크누스-모리스-프랫(Knuth–Morris–Pratt, KMP) 알고리즘은 텍스트 안에서 특정 패턴을 빠르게 찾아내는 대표적인 문자열 검색 알고리즘입니다. 이 알고리즘은 문자를 항상 왼쪽에서 오른쪽 방향으로 검사하며, 패턴 내부에 반복되는 부분 구조(접두사와 접미사가 일치하는 구간)가 있을 때 그 성질을 활용해 이미 수행한 비교 정보를 재활용합니다. 덕분에 최악의 경우에도 선형 시간 안에 검색을 마칠 수 있습니다.
KMP 알고리즘의 시간 복잡도는 O(n)입니다. 단순 무차별 대입(brute-force) 방식의 O(n×m)과 비교하면 텍스트 포인터를 되돌리지 않기 때문에 훨씬 효율적이라 할 수 있습니다.
핵심 아이디어: 접두사 배열(실패 함수)
일반적인 검색 방식에서는 불일치가 발생하면 텍스트의 비교 위치를 한 칸 뒤로 물러나 다시 검사해야 합니다. 반면 KMP는 검색에 앞서 접두사 배열(prefArray)을 미리 계산해 둡니다. 이 배열은 '각 위치까지의 부분 문자열에서, 접두사와 접미사가 일치하는 최대 길이'를 저장합니다.
예를 들어 패턴 "AAAB"의 접두사 배열은 다음과 같습니다.
- index 0 ('A'): 일치하는 접두사 없음 → 0
- index 1 ('AA'): 'A' 일치 → 1
- index 2 ('AAA'): 'AA' 일치 → 2
- index 3 ('AAAB'): 일치하는 접두사 없음 → 0
검색 중 불일치가 발생하면 텍스트 포인터는 그대로 둔 채, 패턴 포인터만 이 배열을 참조해 적절한 위치로 점프합니다. 이 덕분에 전체 비교 횟수가 텍스트 길이에 비례하게 됩니다.
입력 및 출력 예시
Input: Main String: "AAAABAAAAABBBAAAAB", Pattern: "AAAB" Output: Pattern found at location: 1 Pattern found at location: 7 Pattern found at location: 14
알고리즘
1. findPrefix(pattern, m, prefArray) — 접두사 배열 생성
입력 − 패턴 문자열, 패턴의 길이 m, 접두사 위치를 저장할 배열
출력 − 각 위치별 접두사·접미사 일치 길이가 기록된 배열
Begin
length := 0
prefArray[0] := 0
for all character index 'i' of pattern, do
if pattern[i] = pattern[length], then
increase length by 1
prefArray[i] := length
else
if length ≠ 0 then
length := prefArray[length - 1]
decrease i by 1
else
prefArray[i] := 0
done
End
2. kmpAlgorithm(text, pattern) — 문자열 검색
입력: 검색 대상이 되는 본문 텍스트와 찾고자 하는 패턴
출력 − 패턴이 발견된 위치들
Begin
n := size of text
m := size of pattern
call findPrefix(pattern, m, prefArray)
while i < n, do
if text[i] = pattern[j], then
increase i and j by 1
if j = m, then
print the location (i-j) as there is the pattern
j := prefArray[j-1]
else if i < n AND pattern[j] ≠ text[i] then
if j ≠ 0 then
j := prefArray[j - 1]
else
increase i by 1
done
End
C++ 구현 예제
#include<iostream>
using namespace std;
void findPrefix(string pattern, int m, int prefArray[]) {
int length = 0;
prefArray[0] = 0; // 첫 번째 위치는 항상 0 (접두사 없음)
for(int i = 1; i<m; i++) {
if(pattern[i] == pattern[length]) {
length++;
prefArray[i] = length;
}else {
if(length != 0) {
length = prefArray[length - 1];
i--; // 반복문 종료 시 i가 증가하는 것을 상쇄하기 위해 감소
}else
prefArray[i] = 0;
}
}
}
void kmpPattSearch(string mainString, string pattern, int *locArray, int &loc) {
int n, m, i = 0, j = 0;
n = mainString.size();
m = pattern.size();
int prefixArray[m]; // 패턴과 같은 크기의 접두사 배열
findPrefix(pattern, m, prefixArray);
loc = 0;
while(i < n) {
if(mainString[i] == pattern[j]) {
i++; j++;
}
if(j == m) {
locArray[loc] = i-j; // (i-j) 위치에서 패턴 발견
loc++;
j = prefixArray[j-1]; // 배열에서 접두사 길이를 가져옴
}else if(i < n && pattern[j] != mainString[i]) {
if(j != 0)
j = prefixArray[j-1];
else
i++;
}
}
}
int main() {
string str = "AAAABAAAAABBBAAAAB";
string patt = "AAAB";
int locationArray[str.size()];
int index;
kmpPattSearch(str, patt, locationArray, index);
for(int i = 0; i<index; i++) {
cout << "Pattern found at location: " <<locationArray[i] << endl;
}
}
실행 결과
Pattern found at location: 1 Pattern found at location: 7 Pattern found at location: 14
본문 문자열 "AAAABAAAAABBBAAAAB"에서 패턴 "AAAB"는 인덱스 1, 7, 14의 세 곳에서 발견됩니다. 이처럼 KMP 알고리즘은 접두사 배열 하나만 사전에 준비하면, 텍스트를 한 번만 순회하면서 모든 패턴 위치를 선형 시간에 찾아낼 수 있습니다.