KMP(Knuth-Morris-Pratt) 알고리즘

  KMP 알고리즘으로 대표적인 문자열(String) 매칭 알고리즘입니다. 문자열 매칭 알고리즘이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘입니다.

 

  KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 '반복되는 연산을 얼마나 줄일 수 있는지'를 판별하여 매칭할 문자열을 빠르게 점프하는 기법입니다.

 

  우리가 구해야 할 것은 위와 같이 접두사와 접미사가 일치하는 최대 길이입니다.

 

길이	문자열	최대 일치 길이
1	a	0
2	ab	0
3	aba	1
4	abac	0
5	abaca	1
6	abacaa	1
7	abacaab	2
8	abacaaba	3

  위와 같이 접두사와 접미사를 구하게 되면 접두사와 접미사가 일치하는 경우에 한해서는 점프(Jump)를 수행할 수 있다는 점에서 몹시 효율적입니다. 이제 위와 같은 접두사와 접미사의 최대 일치 길이는 어떻게 구할 수 있을지 알아봅시다.

 

// 일치했던 부분까지 되돌아가서 다시검사를 하는 방식으로 빠르게
// '최대 일치 길이'테이블을 구축할 수 있습니다.
vector<int> makeTable(string pattern) {
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0);
	int j = 0;
	
	for(int i = 1; i < patternSize; i++) {
		while(j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		} 
		if(pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

int main(void) {
	string parent = "ababacabacaabacaaba";
	string pattern = "abacaaba";
	vector<int> table = makeTable(pattern);
	
	for(int i = 0; i < table.size(); i++) {
		cout << table[i] << " ";
	}
	cout << endl;
}

 

KMP 알고리즘이 문자열을 찾는 과정

출처 : 안경잡이 프로그래머 블로그

출처 : 위와 동일

 

#include <iostream>
#include <vector>

using namespace std;

// 일치했던 부분까지 되돌아가서 다시검사를 하는 방식으로 빠르게
// '최대 일치 길이'테이블을 구축할 수 있습니다.
vector<int> makeTable(string pattern) {
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0);
	int j = 0;
	
	for(int i = 1; i < patternSize; i++) {
		while(j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		} 
		if(pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

void KMP(string parent, string pattern) {
	vector<int> table = makeTable(pattern);
	int parentSize = parent.size();
	int patternSize = pattern.size();
	int j = 0;
	
	for(int i = 0; i < parentSize; i++) {
		while(j > 0 && parent[i] != pattern[j]) {
			j = table[j - 1];
		}
		if(parent[i] == pattern[j]) {
			if(j == patternSize - 1) {
				printf("%d번째에서 찾았습니다.\n", i - patternSize + 2);
				j = table[j];
			}
			else {
				j++;
			}
		}
	}
}

int main(void) {
	string parent = "ababacabacaabacaaba";
	string pattern = "abacaaba";
	vector<int> table = makeTable(pattern);
	
	for(int i = 0; i < table.size(); i++) {
		cout << table[i] << " ";
	}
	cout << endl;
	
	KMP(parent, pattern);
}