[Algorithm] KMP 알고리즘

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

• 패턴을 문장안에서 좌에서 우로 비교하는 것
• 완전 탐색과 다르게 효율적으로 패턴을 찾을 수 있다.
• 패턴과 문장의 불일치가 발생하였을 때 중복 연산을 최대한 피하면서 패턴을 우로 이동시킨다.
  • 문장 불일치 발생 시 얼마만큼 건너뛴뒤에 비교 연산을 진행할 것인지 판단해야함

예시

• 문자열의 부분 문자열과 패턴을 비교하며 문자열 속 패턴의 존재 여부를 알 수 있음
• 문자열에서 "abcac"라는 패턴 찾기

문자열 [... a b c a d ...]
패턴        a b c a c

• 패턴을 찾는 중에 위 상황이 발생 시 
  • abca까지는 맞았지만 그 다음 문자열에서 찾고 있는 패턴이 아님을 알아낸 경우

문자열 [... a b c a d ...]
패턴         a b c a c

• 우로 한칸 옮겨서 다음 위치에서 패턴을 찾을 수 있을  것이다.
• 하지만 한칸 씩 옮기면 문자열과 패턴의 길이가 길어질 경우 많은 시간이 걸릴 것이다.

문자열 [... a b c a d ...]
패턴              a b c a c

• 위 상황의 경우 3칸을 옮길 수 있을 것이다.
• 문자열과 패턴의 매칭이 실패했을 때 매칭을 성공했던 부분을 다시 재활용하는 것이 KMP 알고리즘이다.

용어

• 접두사
  • 문자열의 첫 부분부터 시작하는 부분 문자열
  • "abcab"라는 패턴의 접두사는 "abcab", "abcab", "abcab", "abcab", "abcab" 에서 빨간색인 부분
• 접미사
  • 문자열의 마지막 부분으로 끝나는 부분 문자열
  • "abcab"라는 패턴의 접미사는 "abcab", "abcab", "abcab", "abcab", "abcab" 에서 빨간색인 부분
• 실패 함수
  • 어떠한 문자열에서 접두사와 접미사가 같은 부분 문자열 중에서 길이가 가장 긴 것
  • "abcdabc"에서 실패 함수는 3

Failure Function

• KMP 알고리즘에서 탐색 문자열의 접두사와 접미사의 일치 부분을 계산하여 배열의 형태로 저장하는 함수이다.

i	N[...i]	접두사이면서 접미사인 최대 문자열	F(i)
0	a	X	0
1	ab	X	0
2	aba	a	1
3	abaa	a	1
4	abaab	ab	2
5	abaaba	aba	3

• 실패 함수를 구하는 과정은 다음과 같다.
  • 비교된 탐색 문자열의 부분 중, 접두사이면서 접미사인 최대 문자열을 구하여 배열의 형태로 저장한다.
  • 계산된 배열을 참고하여 탐색 문자열을 이동시킨다.
  • 불일치가 발생한 index가 j라면, 다음 비교를 위해 탐색 문자열의 위치를 F(j-1) index에 위치한다.

Failure Function 코드

void FailureFunction(string pattern)
{
	F[0] = 0;
	int i = 1;
	int j = 0;

	while (i < pattern.size())
	{
		if (pattern[i] == pattern[j])
		{
			F[i] = j + 1;
			i++;
			j++;
		}
		else if (j > 0)
			j = F[j - 1];
		else
		{
			F[j] = 0;
			i++;
		}
	}
}

• 실패함수의 형태는 KMP 알고리즘의 형태와 크게 다르지 않다.
• 반복문에서 i index가 1씩 증가하고, i - j의 값은 1씩 감소한다.
• 반복이 최악의 경우에도 탐색 문자열의 크기의 두배를 초과하지 않기 때문에 실패함수의 수행시간은 O(M)이다.

KMP Algorithm 코드

int KMPmatch(string text, string pattern)
{
	int n = text.size();
	int m = pattern.size();
	FailureFunction(pattern);

	int i = 0;
	int j = 0;
	while (i < n)
	{
		if (text[i] == pattern[j])
			if (j == m - 1)
				return i - j;
			else
			{
				i++;
				j++;
			}
		else
		{
			if (j > 0)
				j = f[j - 1];
			else
				i++;
		}
	}

	return -1;
}

• KMP 알고리즘 코드 반복문에서 i는 1씩 증가하며, i - j 의 값은 최소 1씩 증가한다.
• 반복이 문자열의 크기의 두 배를 넘지 않는다.
  • KMP 알고리즘의 수행시간은 실패함수의 수행시간을 더한 O(N+M)이 된다.

 

 

 

 

출처

https://velog.io/@hwan2da/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-KMP-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] KMP 알고리즘

https://growth-coder.tistory.com/42

[Algorithm] KMP 알고리즘 (문자열 매칭 알고리즘)