KMP 알고리즘 정리

KMP 알고리즘은 ctrl + F 와 같이 긴 문자열에서 특정 패턴을 찾을 때 사용되는 알고리즘이다. 

 

단순히 하나씩 검색 시, 검색 대상 문자열 길이가 N, 검색 패턴 길이가 M일 때 O(NM) 이 소요되지만, KMP를 이용 시 O(N+M)이 소요된다. 

 

KMP 알고리즘은 다음과 같이 동작한다. 

- 실패 함수를 통해 패턴의 prefix와 suffix의 일치하는 최대 길이를 계산

- 계산된 실패함수를 바탕으로 패턴 매칭 실패 시 suffix 위치로 이동

 

실패 함수 (아래에서 pi 함수)

ababaabbabab 와 같은 패턴이 있을 때, prefix와 suffix의 공통 최대 길이를 구하는 함수이다. 

ababaabbabab의 경우, abab / aabb / abab 와 같이 prefix와 suffix의 공통 부분은 abab이다. 

 

이와 같이 주어진 패턴의 각 index 까지 substring이 있을 때, prefix와 suffix의 최대 공통 부분의 길이를 구하는 것이 pi 함수이다. 

 

예를 들어 위 ababaabbabab의 경우 pi 는 다음과 같다. 

a : 0

ab : 0

aba : 1

abab : 2

ababa : 3

ababaa : 1

ababaab : 2

ababaabb : 0

ababaabba : 1

ababaabbab : 2

ababaabbaba : 3

ababaabbabab : 4

 

이를 이용해 검색하고자 하는 문자열에서 검색이 실패한다면, suffix가 일치했던 곳으로 바로 이동하는 것이 KMP 알고리즘의 핵심이다. 

 

예를 들어 abaababaabbabab  와 같은 문자열이 있다고 해보자. ( aba / ababaabbabab )

처음 검색 시, aba 부분만 일치하게 된다. 이 때 다음 탐색을 b부터 탐색하는 것이 아닌, aba의 공통 prefix, suffix 위치인 세 번째 a로 옮겨가 검색을 진행한다. 

 

이와 같이 prefix와 suffix가 공통인 부분을 미리 알고 있다면, 굳이 하나씩 체킹하는 것이 아닌, 일치하는 suffix 부분으로 바로 넘어가도록 하는 것이다. 

 

코드는 다음과 같다. 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> getPi(const char pattern[])
{
	int m = strlen(pattern);
	vector<int> pi(m, 0);
	
	int i = 1; // pattern의 1번째부터 
	int j = 0; // 현재 탐색 길이 
	
	while(i < m) {
		if(pattern[i] == pattern[j]) {
			j++;
			pi[i] = j;
			i++;
		}
		else {
			// 불일치 케이스 
			if(j != 0)
				j = pi[j-1];
			else {
				pi[i] = 0;
				i++;
			} 
		}
	} 
	
	return pi;
}

vector<int> KMP(const char text[], const char pattern[])
{
	vector<int> res;
	
	int n = strlen(text);
	int m = strlen(pattern);
	
	vector<int> pi = getPi(pattern);
	
	int i = 0; // text index
	int j = 0; // pattern index
	
	while(i < n) {
		if(pattern[j] == text[i]) {
			i++;
			j++;
		}

		if(j == m) {
			// pattern 일치 
			res.push_back(i - j);
			j = pi[j-1];		 
		}
		else if(pattern[j] != text[i]) {
			if(j != 0)
				j = pi[j-1];
			else 
				i++;
		}
	}
	
	return res;
}

int main()
{
	char *text = "abcdefg bcd def ggg fff efg";
	cout << "text : " << text << "\n";
	
	vector<char*> patterns;
	patterns.push_back("abc");
	patterns.push_back("bcd");
	patterns.push_back("def");
	patterns.push_back("efg");
	
	for(auto p : patterns) {
		cout << "pattern : " << p << "\n";
		cout << "pos : ";
		
		vector<int> pos = KMP(text, p);
		for(auto v : pos) {
			cout << v << " ";
		}
		cout << "\n";
	}
}

 

결과