[알고리즘] KMP 알고리즘

문자열 $N$ 와 $H$가 주어졌을 때 $N$에 $H$ 있는지 찾는 문자열 검색 알고리즘에 대해 알아보자. 

 

나이브하게 접근해보면 $N$의 첫문자부터 마지막문자까지 $H$와 하나하나 비교해가면서 일치하는지 판별할 수 있고 해당 솔루션의 시간복잡도는 $O(|N|*|H|)$ 이다. 

문자열의 길이가 짧다면 해당 접근방법도 구현도 쉽고 나쁘지만은 않다. 하지만 문자열의 길이가 커진다면 제한시간내에 동작하지 못하게 된다.  

 

$N[k...i-1]$과 $H[...i-1]$ 까지는 문자열이 일치하였지만 $H[i]$ 문자에서 일치하지 않는경우 다시 $N[k+1]$ 부터 비교하는 것이 아니라 이미 $H[...i-1]$까지 어떤 문자가 있는지 알고 있으니 보지 않아도 $H[k+1]$이 $H[0]$과 같은지 다른지는 알 수 있지 않을까? 라는 아이디어에서 온 것이 바로 KMP 알고리즘 이다. 

 

커누스 모리스 프랫 (Knuth Morris Pratt) - KMP 알고리즘

KMP 알고리즘은 실패 함수를 만들어서 문자열 비교 실패시 다음 시작 위치를 어디로 잡아야 할지 알려준다. 

 

$pi[i] = N[...i]$의 접두사도 되고 접미사도 되는 문자열의 최대 길이

 

$N$ = "aabaabac" 일때 실패함수 pi가 어떻게 구성되는지 살펴보자. 

 

$i$	$N[...i]$	접두사이면서 접미사인 최대 문자열	$pi[i]$
0	a	없음	0
1	aa	a	1
2	aab	없음	0
3	aaba	a	1
4	aabaa	aa	2
5	aabaab	aab	3
6	aabaaba	aaba	4
7	aabaabac	없음	0

 

여기서 중요한 점은 시작 위치를 움직인 이후 첫 글자부터 다시 대응시킬 필요가 없다는 것이다.  

 

아래의 코드는 실패 함수 구현 코드이다. 

 

 

def kmp(n, string, pattern):
    pi = [0]*n
    i = 0
    for j in range(1, n):
        while i > 0 and pattern[i] != pattern[j]:
            i = pi[i-1]
        if pattern[i] == pattern[j]:
            i += 1
            pi[j] = i
    return pi

 

실패 함수를 구현했다면 해당 배열을 가지고 문자열 비교하는 아이디어는 실패 함수 만들었던 아이디어와 같다.

 

-작성중-.