1. KMP 알고리즘이란?
문자열 검색 알고리즘 중에 하나로 주어진 문자열에서 특정 문자를 모두 찾아내는 알고리즘입니다.
쉽게 생각해서 우리가 흔히 사용하는 Ctrl + F 를 수행할 수 있는 알고리즘이라고 생각하면 됩니다.
이 알고리즘의 이름은, 이 알고리즘을 고안한 세 명의 컴퓨터 과학자인 커누스(Donald Ervin Knuth), 모리스(James Hirram Morris), 프랫(Vaughan Ronald Pratt)의 앞글자를 따서 이름 붙었습니다.
https://ko.wikipedia.org/wiki/커누스-모리스-프랫_알고리즘
커누스-모리스-프랫 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다. 문자열
ko.wikipedia.org
2. 기본적인 문자열 검색 방법
주어진 문자열과 비교할 단어를 이중 for 문으로 일일이 확인하는 방법입니다.
예를 들어 문자열 ABABAABAC 가 있고, ABAB 를 찾는다고 해봅시다.
1) 첫 번째 탐색 - 일치
| A | B | A | B | A | A | B | A | C |
| A | B | A | B |
2) 두 번째 탐색 - 불일치
| A | B | A | B | A | A | B | A | C |
| A |
3) 세 번째 탐색 - 불일치
| A | B | A | B | A | A | B | A | C |
| A | B | A | B |
4) 네 번째 탐색 - 불일치
| A | B | A | B | A | A | B | A | C |
| A |
5) 다섯 번째 탐색 - 불일치
| A | B | A | B | A | A | B | A | C |
| A | B |
6) 여섯 번째 탐색 - 불일치
| A | B | A | B | A | A | B | A | C |
| A | B | A | B |
문자열의 길이가 m, 찾는 단어의 길이가 n이라고 했을 때, 이렇게 검색할 경우 시간복잡도는 \(O(m \times n)\)입니다.
3. 실패 함수
위 탐색 단계를 잘 살펴보면 굳이 탐색할 필요가 없는 단계가 있습니다.
첫 번째 탐색을 살펴보면 우리가 검색해야 할 단어 ABAB 가 모두 일치했습니다.
ABAB는 AB 가 두 번 반복되므로, 두 칸을 건너뛰어 바로 세 번째 탐색으로 진행해도 될 것 같습니다.
심지어 앞의 AB는 볼 필요도 없고, 뒤 두 칸만 AB와 일치하는지 보면 됩니다.
같은 원리로 세 번째 탐색을 살펴보면 ABA가 일치했습니다.
ABA는 앞뒤로 A가 반복되므로, 역시 두 칸을 건너뛰어 바로 다섯 번째 탐색으로 진행해도 될 것 같습니다.
역시 이미 일치했던 A를 제외하고 뒤의 세 칸이 BAB와 일치하는지 확인하면 됩니다.
잘 보면 단어의 일치한 부분 중 접두사(prefix)와 접미사(suffix)가 같은 부분이 있다면 점프할 수 있다는걸 알 수 있습니다.
이처럼 다음 탐색을 해야할 때(보통 탐색에 실패했을 때), 얼마나 점프를 해야하는지 알려주는 함수를 실패 함수라고 부릅니다.
그리고 이 실패 함수를 구현하기 위해 필요한 표를 pi배열이라고 부릅니다.
pi배열은 탐색할 문자를 처음부터 각 인덱스까지의 부분 문자열로 나누어, 같은 접두사와 접미사의 최대 길이를 가집니다.
앞에서 살펴본 ABAB 의 pi배열을 만들면 다음과 같습니다.
| 인덱스(i) | i 까지의 부분 문자열 | 접두사 == 접미사 | pi[i] 또는 F(i) |
| 0 | A | 없음 | 0 |
| 1 | AB | 없음 | 0 |
| 2 | ABA | A | 1 |
| 3 | ABAB | AB | 2 |
그렇다면 pi배열은 어떻게 만들까요?
재미있게도 pi배열을 만들 때에도 앞에서 살펴본 건너뛰기 방법을 사용할 수 있습니다.
위키피디아의 pseudo code를 보면 다음과 같습니다.
vector<int> KMP_GET(string grope){
int Begin=0, Length = (int)grope.size();
vector<int> pi(Length, 0);
for(int i=1 ; i< Length ; i++){
while(grope[i] != grope[Begin] && Begin > 0)Begin = pi[Begin-1];
if(grope[i] == grope[Begin]) pi[i] = ++Begin;
}
return pi;
}ABAB 보다 좀더 복잡한 문자열인 ABABABC로 예를 들어보겠습니다.
1) 문자열을 한 칸 밀어 원래 문자열과 비교합니다. 다르면 문자열을 한 칸 더 밀어 비교합니다.
| 인덱스(i) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| pi[i] | 0 | 0 | ||||||
| 문자열(기준) | A | B | A | B | A | B | C | |
| Begin | 0 | |||||||
| 문자열(비교) | A | B | A | B | A | B | ... |
2) 문자열과 비교해서 같은 경우에는 숫자를 1씩 늘려가며 입력합니다.
| 인덱스(i) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| pi[i] | 0 | 0 | 1 | 2 | 3 | 4 | ||
| 문자열(기준) | A | B | A | B | A | B | C | |
| Begin | 0 | 1 | 2 | 3 | 4 | |||
| 문자열(비교) | A | B | A | B | A | ... |
3) 같은 부분이 있었다가 달라지는 경우에는 기존에 만들어 둔 pi배열을 활용합니다. 위에서는 비교 문자열 3까지 같았으므로 pi[3]이 Begin이 됩니다.)
| 인덱스(i) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| pi[i] | 0 | 0 | 1 | 2 | 3 | 4 | ||
| 문자열(기준) | A | B | A | B | A | B | C | |
| Begin | 0 | 1 | 2 | |||||
| 문자열(비교) | A | B | A | ... |
4) 위의 과정을 반복하다가 결국 첫 번째 문자마저 다르면 다음으로 넘어갑니다.
| 인덱스(i) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| pi[i] | 0 | 0 | 1 | 2 | 3 | 4 | 0 | |
| 문자열(기준) | A | B | A | B | A | B | C | |
| Begin | 0 | |||||||
| 문자열(비교) | A | ... |
모든 부분 문자열의 접두사와 접미사를 일일이 비교해가며 구하는 방법은 \(O(n^{3})\)이 걸리지만, 이 방법은 \(O(n)\)입니다.
