2018년 12월 27일 목요일

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];
  }
}