두개의 문자열이 일치하고 있는 경우
이 문자열을 비교하는 경우 몇 칸을 이동하면 suffix 와 prefix 가 일치할까?
이는 문자열
abcabc에서 suffix 중에서 최대 prefix 를 구하는 문제이다. 이 것이 패턴을 전처리 하는 과정이다. KMP 방법은 찾고자 하는 pattern 을 조작하여 속도를 높이는 방법이다.몇 가지 예를 들어 보면
이를 구하는 방법이 분류 3 의 패턴의 전 처리 방법이다.
- a b c a b c a b c 이면
a b c a b c a b c a b c a b c a b c- a b c a 이면
a b c a a b c a
KMP 알고리즘은 찾고자 하는 패턴을 미리 전 처리하여 이러한 정보를 구한 후 한 칸이상을 움직여 비교하여 속도를 높이는 방법이다.예를 들어,
- 대상이 되는 text 가 아래와 같고
text: a b c a b a b .............................- 위에 있는 문자열 중에 아래와 같은 패턴을 찾고자 한다면
pattern: a b c a b c
- step1.
a b c a b a b . . . a b c a b c ---------------------- o o o o o xx 부분에서 틀려진다. 무식(?)하게 하면 한 칸 이동 후 다시 비교 해야 하지만 이 때 한 칸 밀 필요 없이 a b c a b c 에서 suffix 의 최대 prefix 를 구한 상태이므로 3 칸을 밀 수 있다.
왜 이렇게 할 수 있을까? 이 부분이 KMP 의 핵심 아이디어다.
일치하는 문자 a b c a b 에서
a b c a b a b c a b이므로 성큼 밀어 버릴수가 있다.
- step2.
a b c a b a b . . . a b c a b c- step3.
...
패턴이 아래와 같다면
a b c a b c a a
구하고자 하는 결과 배열은 아래와 같다.
문자 위치 0 1 2 3 4 5 6 7 패턴 문자 a b c a b c a a 인덱스 -1 -1 -1 0 1 2 3 0 -1 인 경우 일치하는 부분이 없다.
- 문자 위치 3 이 0 인 이유는
a b c a a b c a 0 1 2 3- 문자 위치 4 가 1 인 이유는
a b c a b a b c a b 0 1 2 3 4설명---
패턴의 suffix , prefix 가 두개의 사각형모양으로 일치한다고 하자.
다음 진행에서 두가지 경우가 발생할 수 있다.
- 일치하는 경우(그림에서는 동그라미 , 동그라미)
이 경우는 간단히 오른쪽 동그라미에 왼쪽의 동그라미의 위치를 저장하면 된다.
- 일치하지 않는 경우(그림에서는 동그라미 , 사각형)
이 경우는 네모위치에 동그라미가 있다고 생각 후 같은 방식으로 생각하면 된다. (이 부분 조금 생각해야 합니다)
그림으로 설명하면
예를 들어 ,
- 그림에서는 한 번 더 접근할 시에 동그라미가 나타나는 경우이다.
왼쪽의 파란사각형과 오른쪽의 파란사각형의 패턴이 일치
a b a d ... a b a ----- -----에서 다음 문자로 b 가 오면a b a d ... a b a b ----- -----b 와 d 가 같지 않다.d 앞에 a 가 있고 이는 0 번째 a 를 가리키고 있으니 0 번째 문자 다음 문자를 보니 b 이므로
a b a b 의 b 위치에는 두 번째(위치로는 1)를 가리키면 된다.
::패턴을 전 처리하는데 필요한 시간 복잡도 : O(n)