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

문자열 비교 알고리즘 중 단순 비교 알고리즘보다 효울적인 알고리즘이다.

 

먼저 단순 비교 알고리즘은 패턴을 옆으로 하나하나 옮겨가며 비교하는 알고리즘인데, 

생각해보면 문자열의 길이 n, 패턴의 길이 m 이라고하면 O(nm)이라는 시간복잡도가 나올 수 있다.

즉, 문자열과 패턴의 길이가 길면 길수록 시간복잡도는 커진다.

 

그래서 KMP 알고리즘은 모든 경우를 다 비교하지 않아도부분 문자열을 찾을 수 있는 알고리즘이다.

Idea. 일치하지 않는 부분 이전까지 한 번에 위치를 옮기면 어떨까?

 

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

--> 참고로, 나는 접두사 접미사 개념을 겨우겨우 진짜 이해했다. 여기서 실패 함수(Failure Function)이라는 개념이 들어가는데, 진짜 이해하는데 힘들었다.

 

먼저 실패함수는 불일치가 발생했을 때, 실패했을 때 어떻게 해야하는 지 값을 알려주고 있어 실패함수라고 부른다.

 

실패 함수

 실패 함수는 중요하다고 하는데, 알고리즘 초보인 나는 실패 함수를 많이 본 적은 없다.

여기서 접두사, 접미사 개념을 적용하게 되는데, 다른 블로그에서 그림으로 아주 설명이 잘되어있다.

 

KMP알고리즘

 문자열을 H, 패턴을 S 그리고 H에서 시작 인덱스를 begin으로, 일치하는 개수를 m으로

- H[begin+m] == S[m] : m++

- H[begin+m] != S[m] : 여기서 실패 함수값이 적용되어 점프한다. 

EX)

0. m =3 으로 3번째 인덱스에서 불일치가 발생했다고 가정하면,  m-1개까지 는 일치했다고 볼 수 있다.

1. 여기서 실패 함수를 F(m)라고 가정하면, F(m-1) 를 계산한다. 

2. 그래서 F(2) = 1 이라고 가정한다. --> 일치한 문자열 까지에서 접두사와 접미사가 일치하는 부분이 1개라는 뜻.

3. m = 1 로 초기화 해준다. m = F(m-1)이 되는 것을 확인. --> 위에서 F(2) = 1이 나와서 그런거임.

4. begin 값을 begin = begin + m - F(m-1) 으로 계산하면된다. 

#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";

	KMP(parent, pattern);

	return 0;
}