여기서는 KMP 자체보다는 핵심인 Failure function 에 대한 설명만 한다.
F 함수를 재귀로 디게 어렵게 설명한다음 뭐 어려운 것이다
원래 한번에 이해가 안되는게 당연하다고 하는데
혼자 해 보니까 사실 어려운 개념이 아니었다.
F(i) 함수의 정의 :
문자열에서 1 ~ i 까지 항목을 고려했을 때,
접두사와 접미사가 같은 최대의 길이.
즉, ABABA 를 생각해 보자.
F(1) 은 1 항목 (A) 를 고려해 보면 접두사와 접미사가 같은 최대 길이가 0 이다.
F(2) 는 2 항목 (AB) 까지 고려해 보면 A랑 B가 다르니까 0 이다.
F(3) 는 3 항목 (ABA) 까지 고려해 보면 첫 A와 마지막 A 가 같으니까 길이가 1이다.
F(4) 는 4 항목 (ABAB) 까지 고려해 보면 AB와 AB 가 같으니까 길이가 2이다.
F(5) 는 5 항목 (ABABA) 까지 고려해 보면 ABA와 ABA 가 같으니까 길이가 3이다.
그러면 F 함수에 대한 규칙을 찾을 수 있다.
화살표 두개로 시작해서, 일치하기 시작하면
앞쪽 화살표 부분에서는 F 함수에 1씩 더하고,
뒤쪽 화살표는 쫓아가는 모습이라고 생각하면
바~~로 이해되는 부분이다.
|
↓
|
↓
|
|
|
|
|
A
|
B
|
A
|
B
|
A
|
|
0
|
0
|
|
|
|
|
↓
|
|
↓
|
|
|
|
A
|
B
|
A
|
B
|
A
|
|
0
|
0
|
1
|
|
|
|
|
↓
|
|
↓
|
|
|
A
|
B
|
A
|
B
|
A
|
|
0
|
0
|
1
|
2
|
|
( 앞쪽 A는 이미 비교해서 맞았기 때문에 다시 비교할 필요가 없다. )
|
|
|
↓
|
|
↓
|
|
A
|
B
|
A
|
B
|
A
|
|
0
|
0
|
1
|
2
|
3
|
그럼 뒤쪽 화살표가 쫓아가다가 틀렸다면 ?
불쌍하게도 뒤쪽은 다시 처음부터 비교 시작이다.
이제 긴 예제를 들어보자
|
↓
|
↓
|
|
|
|
|
|
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
|
|
|
|
|
|
|
|
|
|
|
↓
|
|
↓
|
|
|
|
|
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
|
|
|
|
|
|
|
|
|
|
↓
|
|
|
↓
|
|
|
|
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
|
|
|
|
|
|
|
|
|
↓
|
|
|
|
↓
|
|
|
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
|
|
|
|
|
|
|
|
|
↓
|
|
|
|
↓
|
|
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
|
|
|
|
|
|
|
|
|
↓
|
|
|
|
↓
|
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
|
|
|
|
|
|
|
|
|
↓
|
|
|
|
↓
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
!
|
|
|
|
|
|
↓
|
|
|
|
|
|
|
↓
|
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
1
|
|
|
|
|
|
|
↓
|
|
|
|
|
|
|
↓
|
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
1
|
2
|
|
|
|
|
|
|
↓
|
|
|
|
|
|
|
↓
|
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
1
|
2
|
3
|
|
|
|
|
|
|
↓
|
|
|
|
|
|
|
↓
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
1
|
2
|
3
|
!
|
|
|
↓
|
|
|
|
|
|
|
|
|
|
↓
|
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
1
|
2
|
3
|
1
|
|
|
|
↓
|
|
|
|
|
|
|
|
|
|
↓
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
1
|
2
|
3
|
1
|
!
|
|
↓
|
|
|
|
|
|
|
|
|
|
|
↓
|
|
B
|
A
|
C
|
C
|
B
|
A
|
C
|
B
|
A
|
C
|
B
|
C
|
|
0
|
0
|
0
|
0
|
1
|
2
|
3
|
1
|
2
|
3
|
1
|
0
|
아주 개념 이해가 바로 되어 버리지 않았는가?
짝짝짝 !
그리고 코드는 이렇게나 짧다 !
다만, 코드를 이해하는것은 쉽지 않으니
찬찬히 따라가 보자!
void kmp(char *p) {
int n = strlen(p);
int i = -1, j = 0;
int F[MAX_LEN];
F[0] = -1;
while (j < n) {
if (i == -1 || (i >= 0 && p[i] == p[j])) F[++j] = ++i;
else i = F[i];
}
}
글
