개요
KMP 알고리즘은 3명의 학자(Knuth-Morris-Pratt)가 만든 문자열 탐색 알고리즘입니다. 문자열(S)에서 문자(W)를 찾을 때 사용하는 알고리즘으로, O(|S| + |W|)의 시간복잡도를 가지는 어마어마한 알고리즘입니다. |S|와 |W|는 각각 문자열의 길이를 의미하며, 전체 시간 복잡도가 문자열과 문자 길이의 합이라는 건 단 1번의 탐색으로 문자열 속 문자를 모두 찾을 수 있다는 의미로, 매우 효율적인 탐색 알고리즘 중 하나입니다. 그럼 도대체 어떤 방식으로 탐색해서 이렇게 효율적인지 한번 알아봅시다.
알고리즘
영문 위키피디아의 예시를 통해 기본적인 알고리즘 구조를 살펴보겠습니다. 우선 문자열 S = "ABC ABCDAB ABCDABCDABDE"에서 문자 T = "ABCDABD" 를 탐색해보겠습니다. 탐색 초기에는 다음과 같이 3개의 문자("ABC")가 동일합니다.
| S | A | B | C | A | B | C | D | A | B | C | D | A | B | D | B | C | D | A | B | D | E | ||
| T | A | B | C | D | A | B | D |
하지만 4번째 문자는 S와 T가 서로 다른 문자라는 걸 볼 수 있습니다. 첫 번째 위치에 T를 두었을 때 탐색에 실패하였으니 다음에는 T를 1칸 이동해서 2번째 위치에 T를 두고 탐색을 하면 될까요? 물론 말리지는 않겠지만 우리는 이렇게 탐색을 할 경우에는 무척이나 오랜 시간이 걸린다는 건 눈치챌 수 있습니다. T를 배치할 수 있는 위치마다 T의 길이만큼 탐색을 하니 대략 O(N2) 시간복잡도를 가진 알고리즘이며, 만약 S와 T가 100,000자리 문자열과 문자인 경우에는 탐색을 끝내는데 오랜 시간이 걸리게 됩니다.
단순히 브루트포스 알고리즘으로는 긴 문자열 속에서 긴 문자를 찾는데 한계점이 있습니다. 효율적인 알고리즘을 위해서는 문자열 T를 분석해서 탐색에 활용해야 합니다. T를 잘 보면 S와 비교해서 3번째 문자까지는 동일한 문자임을 확인했습니다. 그리고 앞서 비교한 3개의 문자 "ABC"를 관찰해보면 모두 서로 다른 문자입니다. 따라서, 우리는 T의 위치를 2번(B)이나 3번(C)으로 이동해봤자 탐색에 실패할 것이라는 결론을 도출할 수 있습니다. 그렇기에 T는 바로 4번째 위치로 옮겨서 다시 탐색해주면 됩니다. 이렇게 T의 특징을 바탕으로 적절한 위치에 T를 옮겨주는 것이 KMP 알고리즘의 핵심이라고 할 수 있습니다.
그럼 이번에는 다음과 같은 상황이라고 가정해봅시다. 이번에는 T의 위치를 어디로 옮겨야 할까요?
| S | A | B | C | A | B | C | D | A | B | C | D | A | B | D | B | C | D | A | B | D | E | ||
| T | A | B | C | D | A | B | D |
이번 탐색에서는 아쉽게도 마지막 문자에서 서로 다르다는 걸 확인했습니다. 그럼 탐색에 실패했으니 T의 위치를 탐색이 실패한 위치인 11번째 위치(C)로 옮겨야 할까요? 만약 그렇게 알고리즘을 설계한다면 정답을 구할 수 없습니다. 문자 T의 모습을 좀 더 관찰해봅시다. 현재 마지막 문자인 "D"에서 탐색이 실패했습니다. 그렇다는 건 이전의 문자들은 모두 동일하다는 의미이며, 우리는 여기서 문자 T에서 가장 앞에 위치한 "AB"가 중간에 1번 더 나온다는 점을 활용할 수 있습니다. "AB"가 한번 더 나온다는 의미는 T의 시작 위치를 두 번째 "AB"가 시작하는 위치로 옮기면 3번째 문자부터 확인해도 된다는 의미입니다. 따라서, T의 위치를 9번째 위치(A)로 옮겨보면 드디어 문자 T를 찾을 수 있습니다.
| S | A | B | C | A | B | C | D | A | B | C | D | A | B | D | B | C | D | A | B | D | E | ||
| T | A | B | C | D | A | B | D |
이렇게 T의 시작 위치를 적절하게 바꿔주면서 효율적으로 문자열을 탐색하는 알고리즘이 바로 KMP 알고리즘입니다. KMP 알고리즘에서는 문자 T를 분석해서 탐색에 실패했을 경우, 적절한 탐색 위치를 알려주는 실패함수를 전처리 과정을 통해 구한 다음, 문자열 S를 하나씩 살펴보면서 T가 포함되었는지 확인하는 과정을 거치게 됩니다. 그리고 만약 탐색에 실패한 경우에는 미리 구해둔 실패함수를 통해 T의 시작 위치를 점점 오른쪽으로 보내게 됩니다. 그리고 문자열 S의 끝에 다다르면 알고리즘이 종료하게 됩니다.
소스코드
소스코드는 백준의 1786. 찾기 예시 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <stdio.h>
#include <vector>
#define NMAX 1000010
using namespace std;
char T[NMAX], P[NMAX];
vector< int > ans;
int tlen, plen;
int fail[NMAX];
int main() {
fgets(T, NMAX, stdin);
fgets(P, NMAX, stdin);
for(int i=0;T[i]!='\n';i++) tlen++;
for(int i=0;P[i]!='\n';i++) plen++;
// 실패함수 만들기
// i: 접미사(뒤에 추가되는 문자) / j: 접두사(지금까지 일치했던 접두사의 마지막 문자)
for(int i=1, j=0;i<plen;i++) {
// 겹치는 문자열이 있는지 확인
while(j>0 and P[i]!=P[j]) j = fail[j-1];
// 동일한 문자열이 반복이라면 다음 문자부터 탐색하기
if(P[i] == P[j]) fail[i] = ++j;
}
// KMP 알고리즘
for(int i=0, j=0;i<tlen;i++) {
while(j>0 and T[i] != P[j]) j = fail[j-1];
if(T[i] == P[j]) {
j++;
if(j == plen) {
ans.push_back(1 + (i-plen+1)); // 번호가 1번부터 매겨짐
j = fail[j-1];
}
}
}
// 출력
printf("%d\n", (int)ans.size());
for(int val:ans) printf("%d ", val);
}
|
cs |