kmp는 π배열이라는 도구를 활용함.

π배열 정의

π[i] = max{ k ∣ 1≤k<i and S[0:k−1] ≡ S[i−(k−1):i] } π[i]는 인덱스 i에서 끝나는 접두사의 접미사 중 전체 문자열 S의 접두사와 일치하는 가장 긴 접미사의 길이이다. (이 조건을 만족하는 문자열 중 하나는 위치 i에서 끝나는 접두사이다. 그러나 이 경우는 명백히 제외한다.)

aabaaab인 문자열 S가 있다고 할때, 파이 배열은 다음과 같다. π = [0, 1, 0, 1, 2, 2, 3] a 0 aa 1 aab 0 aaba 1 aabaa 2 aabaaa 2 aabaaab 3

π배열 과정 요약

조건을 만족하는 접두사 길이를 j라고 하겠다. 인덱스 i+1를 탐색할 때, π[i] 값을 확인한다. 이는 i까지의 부분 문자열의 길이 π[i]인 접미사가 전체 문자열의 길이 π[i]인 접두사와 동일하다는 의미이다. 따라서 인덱스 π[i] 문자와 인덱스 i+1 문자가 같다면 한 문자만큼 일치된 길이가 증가한다. π[i+1] = π[i]+1 if S[π[i]] == S[i+1]

만약 같지 않다면 j<π[i]인 가장 큰 j를 찾아야 된다. j = π[π[i]-1]
S[0:j−1] ≡ S[i−j+1:i]인 j에 대해 인덱스j와 i+1 문자가 같지 않으면 더 작은 j를 찾아 반복하고 찾으면 종료한다.

kmp π배열을 활용하는 과정

ABCDABCDABDE에서 ABCDABD 찾는다고 할 때,

ABCDABCDABDE ABCDABD i=5인 B까지는 같지만 i=6에서 문자가 불일치한다. 만약 완전탐색을 한다면 i=1에서부터 다시 ABCDABD와 비교하면서 찾아야되고 이는 O(n^2)이다.

하지만 ABCDABD의 π배열을 활용하면 불필요한 연산을 생략할 수 있다. π = [0, 0, 0, 0, 1, 2, 0]

i=5까지 일치하였다는 것을 확인하였다. 그렇다면 만약 i=5에서 끝나는 접두사에서 길이와 형태가 동일한 접두사와 접미사가 존재한다면 해당 부분문자열 다음 인덱스부터 탐색해도 무방하다. 그리고 그것을 π배열를 통해 알 수 있다.

ABCDABCDABDE 'ABCDAB' D π[5] = 2이므로 i=5에서 끝나는 접두사의 앞뒤 AB가 같다는 것을 알 수 있고 이를 π배열을 통해 보장할 수 있다.

ABCDABCDABDE ABCDABD 따라서 BCD 중간 부분은 필요없는 정보이기에 볼 필요가 없다.