KMP String Matching Algorithm은
Knuth-Morris-Pratt의 약자입니다..
예를 들어볼까요.
abcabca : 길이 L
abc : 길이 M
abcabca에서 abc의 개수는 몇개일까요?
종종 우리가 하는 방법이 일일히 길이 L에 대해서 M을 쫙 다 보는거죠.
우리가 하는 방법이 시간복잡도 O(LM)입니다.
그런데 KMP를 이용하면 O(L)에 이것을 구할수 있습니다.
우선 KMP String Matching에는 Pi 배열이 있는데, 이것을 먼저 미리 만들어놓아야 O(L)에 해결가능합니다.
Pi 배열의 정의는 다음과 같습니다.
Pi[i] :
위에서 [abc]와 같이 개수를 알고자 하는 대상에 대해서 고려할 때,
그 대상이 1 ~ i까지 스트링이 존재할 때, 접미사와 일치한 최장 접두사의 끝자리 위치
(단, Pi[i] ≠ i)
예를 들어서, ababaca라는 배열이 있다고 가정해 봅시다.
이 배열의 Pi[5]는 3입니다.
왜 3이 나오는지 볼까요.
Pi의 정의에서 "1 ~ i까지 스트링이 존재할 때"라고 했으므로
ababa에 대해서 고려해야 합니다.
ababa에서, 접미사와 일치한 최장 접두사는 aba입니다.
접미사 aba와 접두사 aba가 일치하지요.
종종 ababa에서 접미사와 일치한 최장접두사는 자신, ababa가 아니냐.. 라고 하는데
위의 조건에 Pi[i] ≠ i라고 굵게 써놓았습니다.
이제 이것이 왜 O(L + M)에 작동하는지 확인해볼까요.
(M : 몇번 나오는지 알고싶어하는 대상의 길이.)
ababaabcbab에서 ababaca의 개수를 알고 싶다고 해봅시다.
a b a b a a b c b a b
a b a b a c a
a b a b a까지 잘 나가다가 밑줄 친 a와 c에서 달라지죠.
여기서 대개 KMP를 모르시는 분들이 구현하는 방법이 ababaca를 앞으로 한칸 땡기는것인데, 이것은 시간낭비라는 것이죠.
a b a b a a b c b a b
a b a b a c a
여기서 붉은 색으로 된 부분을 봅시다.
ababa에서 뒤 aba와 일치한 접두사의 위치는? Pi[5] = 3이므로 '3' 입니다.
따라서 Pi[5]를 호출하면, 아래와 같이 됩니다.
a b a b a a b c b a b
a b a b a c a
여기서 앞의 aba 부분은 고려해 줄 필요가 없는것이
Pi 배열의 정의를 보면 접미사와 같은 최장 접두사가 저장되어있는 배열이므로
어차피 aba는 위 배열 aba와 같다는 것입니다.
여기서 또 a와 b가 같은 지 봅니다.
다르죠? 그렇다면 이제 Pi[3]을 호출합니다. Pi[3] = 1이겠죠.
a b a b a a b c b a b
a b a b a c a
여기서 앞의 a는 고려해줄 필요는 없습니다. 왜냐하면 접미사와 일치한 부분이기 때문이죠.
다시 a와 b를 비교해줍니다. 다름을 알 수 있습니다.
Pi[1] = 0이므로 이제 아래 배열은 앞의 ababa의 굴레(?)에서 완전히 벗어나게 됩니다.
이런 식으로 전진시켜나가다보면 O(L+M)에 가능함을 알 수 있습니다.
그렇다면, Pi 함수는 어떻게 구하냐.. 이게 관건이겠죠.
이 부분은 간단하므로 아래 의사코드를 참고하시기 바랍니다.
참고적으로, 책은 Introduction to algorithms second edition 원서를 참고했습니다.
여기서 P는 pi 배열을 만들고자 할 때 그 대상 String을 말합니다.
m ← length[ P ]
pi[1] ← 0
k ← 0
for q ← 2 to m
do while k > 0 and P[k + 1] ≠ P[q]
do k ← pi[k]
if P[k + 1] = P[q]
then k ← k + 1
pi[q] ← k
return pi