KMP 쉽게 이해하기 (Failure Function 이해)

여기서는 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];
  }
}