본문 바로가기

알고리즘

KMP(Knuth-Morris-Pratt String Matching Algorithm)

KMP는 문자열 매칭(String Matching) 문제를 해결하는 알고리즘이다. 길이가 $N$인 어떤 문자열 $S$와 $S$에서 찾고 싶은 패턴(길이 $M$) $T$가 있을 때, $T$가 $S$에서 몇 번 등장하며 그 위치가 어디인지를 $O(N+M)$에 해결한다.

 

이러한 문자열 매칭 문제를 푸는 가장 간단한 방법은 $O(NM)$일 것이다. $S$의 각 위치에서 시작하는 substring이 $T$와 일치하는지 확인하는 것이다. KMP 알고리즘은 이 알고리즘에 새로운 아이디어를 추가한다. 바로, 이전에 계산한 정보를 이용할 수 있다는 것이다. $S[i, i+p]$와 $T[0, p]$가 일치하고, $S[i+p+1] \neq [p+1]$이라 하자. 했다고 하자. 그렇다면  $S[j, j+M-1]$과 $T[0, M-1]$이 일치하기 위해서는($i < j \leq i + p$) $T[0, p-j+i]$와 $T[j-i, p]$가 일치해야 한다. 여기서 실패 함수(Failure Fuction)이 등장한다. 어떤 문자열에 대해, 그 문자열의 접두사와 접미사 중 일치하는 쌍의 최대 길이를 생각하자. 당연히 원래 문자열보다 짧아야 한다. 예를 들어, "ababa"는 "aba"가 접두사이자 접미사이므로 답이 3이고, "abcdaea"는 "a"의 길이인 1이 답이다. 이를 $T$의 모든 접두사에 대해 정의하자. 즉, 실패함수 $F[i]$는 $T[0, i-1]$의 접미사와 접두사가 일치하는 가장 긴 길이이다. $F[p+1]=p-j+i+1$일 때 $T[0, p-j+i]$와 $T[j-i, p]$가 일치한다. 이를 이용하면, $T$에 대한 실패 함수가 미리 계산되어 있을 때 $S$와의 매칭을 $O(N)$에 할 수 있다.

 

그렇다면 실패 함수는 어떻게 빠르게 구할까? $M$이 충분히 작다면 $O(M^3)$으로 해도 상관 없다. 그러나 실패 함수는 위와 비슷한 방법을 이용하면 $O(M)$에 구할 수 있다. $F[i]=p$라 하자. 즉, $T[0, p-1]=T[i-p, i-1]$, $p<i$이다. $T[i] = T[p]$라면 $F[i+1]=p+1$이다. 그렇지 않은 경우를 생각해보자. $F[i+1]=k$라 하자($k \leq p$). 이는 $T[0, k-1]=T[i+1-k, i]$라는 것이고, 그렇기 위해서는 $T[p+1-k, p-1]=T[i+1-k, i-1]=T[0, k-2]$이어야 한다. $T[0, k-2]=T[p+1-k, p-1]$이라는 성질이 있으므로 이전까지 계산한 실패 함수를 이용할 수 있다. 이 과정은 시간복잡도가 $O(M)$이다.

 

KMP 알고리즘의 시간복잡도가 $O(N+M)$이라는 것은 아래 코드를 통해 쉽게 확인할 수 있다. p=F[p] 과정을 지나면 p의 값은 1 이상 감소하고, p의 값은 각 for문에서 최대 M-1번, N번 증가한다. 따라서 시간복잡도는 $O(N+M)$이다.

 

아래 링크들을 보고 공부하였다.

https://koosaga.com/156

https://blog.myungwoo.kr/101

https://mygumi.tistory.com/61

https://bowbowbow.tistory.com/6

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260

 

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;

int F[MAXN];

// 길이가 N인 문자열 S, 길이가 M인 패턴 T
vector<int> KMP(char S[], char T[], int N, int M) {
	int p = 0;
	for(int i = 1; i < M; i++) {			// 실패 함수 계산
		while(p && T[p] != T[i]) p = F[p];
		if(T[i] == T[p]) p++;
		F[i + 1] = p;
	}

	p = 0;
	vector<int> ans;
	for(int i = 0; i < N; i++) {
		while(p > 0 && S[i] != T[p]) p = F[p];
		if(S[i] == T[p]) p++;
		if(p == M) ans.push_back(i - M + 1);	// 패턴을 발견한 위치를 ans 벡터에 추가
	}
    	return ans;
}

'알고리즘' 카테고리의 다른 글

FFT (Fast Fourier Transform)  (0) 2021.04.03
Edmond's algorithm (Directed-MST)  (0) 2020.12.30
Suffix Array와 LCP  (0) 2019.10.25
양수 가중치를 가지는 그래프에서 O(V+cE)로 최단경로 구하기  (1) 2019.10.15
0-1 BFS  (0) 2019.10.14