KMP는 주어진 문자열의 부분 문자열 중에서 비교 문자열과 매칭이 되는지 확인하는 알고리즘으로, 문자열 검색 알고리즘 중 하나입니다.
완전탐색의 방식으로는 두 문자열의 처음부터 끝까지 비교했다면,
KMP는 이미 아는 정보를 이용해서 덜(?) 비교 합니다.
구체적으로 어떻게 하는 것일까요?
실패함수라는 것을 이용합니다.
실패함수는 매칭에 실패했을 때, 비교를 생략할 수 있는 범위를 알려주는 함수입니다.
설명을 위해 백준 1786번 문제를 인용하겠습니다.
T라는 문자열과, P라는 문자열이 다음과 같을 때, 첫번째 비교는 다음과 같습니다.
1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
| | | | | | X
P : [ A B C D A B D ]
1 2 3 4 5 6 7
C와 D가 일치하지 않으므로 T가 1일 때는 매칭에 실패했습니다. 하지만, 그전까지는 문자가 일치했으므로, P의 2번째 문자(C)부터 매칭을 확인하면 됩니다.
1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
* * | | | | | ( * : 매칭이 된다는 것을 알고 있음)
P : [ A B C D A B D ]
따라서, O(NM)이 아닌 O(N+M)의 시간복잡도로 문제를 해결 할 수 있게 되는 것입니다.
실패함수의 구현은 다음과 같습니다(코드 출처:위키백과)
pi[i] : i번째에서 매칭에 실패했을 때, 다음 비교를 어디부터 해야 할지 알려주는 함수
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;
}
| GROPE(ABCDABD) | PI |
| A | 0 |
| B | 0 |
| C | 0 |
| D | 0 |
| A | 1 |
| B | 2 |
| D | 0 |