kmp - string matching algorithm
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 중간 부분은 필요없는 정보이기에 볼 필요가 없다.
