KMP알고리즘

드디어 KMP 알고리즘이 이해가 되어 글로 쓸 수 있게됐습니다.

아는거에 그치지 않고 누군가에게 설명할 수 있게 된다면 스스로 진정 이해할 수 있다고 할 수 있겠죠.

남에게 도움이 되는건 덤이구요.

---

KMP알고리즘은 문자열 탐색에 있어서 효율적인 방법이 됩니다.

c의 strstr , cpp의 string::find , java String.find은 기본적으로 선형시간이 걸리는것으로 알려져 있습니다.

cplusplus의 string::find 함수 복잡도는 다음과 같이 설명되어 있군요.

Complexity

Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case).

즉, 최악의 사례로 문자열의 길이만큼 걸릴 수 있다는 것입니다.(찾을 문자열이 맨 뒤에있는 경우)

또 구현되어 있기를 원본 문자열(haystack)에서 i번째 부터 대상 문자열(needle)을 모두 대조하고 맞지 않으면

i+1을 다시 반복하여 찾는 방식으로 구현되어 있습니다.

http://hg.openjdk.java.net/jdk7u/jdk7u6/jdk/file/8c2c5d63a17e/src/share/classes/java/lang/String.java

자바 string클래스의 소스파일입니다. 1715번줄에 indexof 함수가 구현되어 있는데 역시

단순한 방법이 적용되어 있습니다.

(사실 어지간한 보통의 문자열은 단순방법으로도 찾는데는 무리가 없습니다. 

알고리즘에 적용에 있어서 선형정도는 그래도 나은편이니까요)

결국 원본 문자열 H의 원소마다 N문자열을 찾게 되므로 

O(NH)가 될것입니다.

---

하지만 이러한 비효율을 피하기 위해 KMP알고리즘을 이용하면 상황은 훨씬 나아집니다.

이 알고리즘은 needle문자열의 접두사, 접미사가 일치하는 정보를 이용하여 탐색에 이용합니다.

우선 다음 예제를 보겠습니다.

기존의 단순무식 알고리즘과 needle문자열을 비교할 때 생기는 정보를 이용하여

이를 다음 탐색에 이용합니다.

우선 다음과 같은 

Haystack(H) : aabaxyaabaa

 needle(N) : aabaa

이 있다고 가정합니다.

H[...n]은 처음부터 n번까지, 

H[n...]은 n부터 끝까지, 

H[n...m]은 n부터 m을 의미하며 

len( H[n..m])은 n부터m까지의 

문자열 길이를 의미합니다. 파이썬과 비슷하죠

i는 haystack을 위한 인덱스 j는 needle을 위한 인덱스입니다.

0	1	2	3	4	5	6	7	8	9	10
a(i)	a	b	a	x	y	a	a	b	a	a
a(j)	a	b	a	a

H[...3] 과 N[...3]이 일치하나 마지막 H[4] != N[3]입니다.

이 때 i=4로 바로 건너뛰지 않고 접두사와 접미사가 일치하는 정보를 이용하여 i=3으로 건너뜁니다.

0	1	2	3	4	5	6	7	8	9	10
a	a	b	a	x (i)	y	a	a	b	a	a
			a	a (j)	b	a	a

다음의 새로운 탐색시작 위치입니다.

여기서  주목할점은 i=4인데  j=2이라는 점입니다.

이전 정보에서 aaba까지 일치함을 확인했기 때문에 탐색위치는  i=3부터 시작했습니다 하지만

접미사와 접두사가 각각 a이므로 이를 이용해서  i=4로 건너뜁니다(즉 한번의 비교를 건너뜁니다)

j도 마찬가지로 1이를 이용해 1부터 시작하게 되는겁니다.

하지만 운이 좋지않게도 H[4] != N[3]입니다.

0	1	2	3	4	5	6	7	8	9	10
a	a	b	a	x (i)	y	a	a	b	a	a
				a (j)	a	b	a	a

i=j=4 부터 다시 검사를 해야하는데 처음부터 일치하지 않습니다. 이때는 별 수 없이 바로 다음 인덱스를 검사합니다.

0	1	2	3	4	5	6	7	8	9	10
a	a	b	a	x	y	a	a	b	a	a
					a	a	b	a	a

마찬가지로 처음부터 일치하지 않습니다. 다음으로 건너 뜁니다.

0	1	2	3	4	5	6	7	8	9	10
a	a	b	a	x	y	a	a	b	a	a
						a	a	b	a	a

혹여 haystack이 더 길어서 뒤에 있다고 가정하면

맨 처음 배열 상태를 가정하고 반복해보면 되겠습니다.

이러한 과정을 소스코드로 작성하면 다음과 같습니다.

---

마지막으로

일명 실패함수라 불리우는 접두사와 접미사의 정보를 저장할 배열을 만드는 알고리즘이 필요합니다.

단순무식하게 한다면 

needle문자열을 하나하나 대조하면서 완성할 수 있습니다.

물론 대게 needle문자열이 길지는 않으므로 이러한 방법도 무리는 없겠지만

위의 kmp알고리즘을 응용하여 pi함수(혹은 실패함수)를 완성할 수 있습니다.

kmp알고리즘과 거의 비슷합니다. 단지 16번 줄을 보면 pi함수의 현재 차례에 matched를 대입함을 확인할 수 있습니다.

이는 다시 말하면 현재 저장할 값은 이전의 matched값보다 하나 큰 값을 넣는다는 의미입니다.

즉 이전의 일치정보를 그대로 이용한다는 의미입니다.

위의 N문자열인 aabaa를 이용해 그대로 알고리즘을 따라가면 무슨의미 인지 이해가 가실겁니다.

이를 이용해 aabaa의 pi함수를 다음과 같이 작성할 수 있습니다.

i	N[...i]	pi[i]
0	a	0
1	aa	1 (a)
2	aab	0 ()
3	aaba	1 (a)
4	aabaa	2 (aa)