Menu

문서정보

KMP 알고리즘

Knuth-Morris-Pratt 3명이 개발한 알고리즘이다. 보통 첫 글자를 따서 KMP 알고리즘이라고 한다. 이 알고리즘은 문서에서 동일한 문자열을 찾기 위해서 사용한다.

개요

배열 S에서 문자열 W가 몇 개가 있는지를 찾아내는 알고리즘을 만들어 보자. S 배열의 처음부터 W가 일치하는지를 일일이 확인하는 간단한 방법을 생각 할 수 있다. 아래 예제를 보자. S는 "ABC ABCDAB ABCDABCDABDE" W는 "ABCDABD"다.

 Simple Search

S[0]과 W[0]을 비교한다. W[6]까지 비교해서 일치한다면, 동일한 문자열이다. 만약 일치하지 않는다면 S[1]로 이동해서 동일한 과정을 반복한다. 이 방식의 복잡도는 O(MN)이다. 간단하긴 하지만 효율적이진 않다. 효율적인 방법을 찾아보자.

위 그림에서 아이디어를 찾을 수 있다. 단순한 찾기 알고리즘의 문제는 일치했던 정보를 기억하지 않는다는 점이다. 일치했던 정보(여기에서는 배열의 인덱스 값)를 저장하고 있다면, 이 부분을 건너 뛰면 시간을 절약할 수 있을 것이다.

 KMP - 1

W의 인덱스를 증가하면서 S와 비교한다. 인덱스 2까지 일치하고, 인덱스 3에서 실패할 것이다. 그렇다면 다음 비교때는 S[1]부터 시작하지 않고 S[3]부터 시작하면 된다. 따라서 이 알고리즘은 m=3, i=0으로 설정한다.

 KMP - 2

첫번째 문자에서 실패 했으므로 m=4, i=0으로 설정한다.

 KMP - 3

이제 "ABCDAB"까지는 완전일치하고 W[6], S[10]인 "D"에서 불일치 한다. 여기에서 처음 시작 문자열인 "AB"가 W[4-5] 다시 등장하는 걸 알 수 있다. 따라서 다음 비교는 m=8부터 시작해야 한다. 이 알고리즘에서는 처음 문자열이 반복해서 나타나는 지점을 찾는게 중요함을 알 수 있다. 이 문자열 W에서의 Prefix 문자열은 "AB"다. "AB"문자열은 이미 일치했으므로 i=2로 세팅하면 된다.

 KMP - 4

i[2]터 비교한다. W[2]는 C이고 S[10]은 " "이므로 첫 번 비교 부터 매칭되지 않음을 알 수 있다. m=10, i=0로 설정한다. 으로 설정한다.

 KMP - 5

m=10에서 바로 실패한다. 알고리즘에 의해서 m=11, i=0으로 설정한다.

 KMP-6

"ABCDAB"까지 일치했지만 "C"에서 실패했다. 처음 문자열인 "AB"가 중간에 한번 나타났기 때문에 m=15, i=2로 설정한다.

 KMP-7

S[15]에서 완전 일치했다.

접두사 일치 테이블 만들기

KMP 알고리즘은 W="ABCDABD"에서 일치하는 문자열을 찾는 부분과 이 일치하는 부분(Partial match)을 이용해서 목표 문자열에서 검색하는 두 개의 부분으로 이루어진다. Partial match를 효과적으로 수행하기 위한 알고리즘을 만들어 보자. 먼저 아래와 같은 테이블을 만들었다.
i 0 1 2 3 4 5 6
W[i] A B C D A B D
T[i] -1 0 0 0 0 1 2
T[0]=-1로 설정했다(왜 인지 생각해보자).

.... 계속