[박혜웅] Knuth-Morris-Pratt(KMP)

• Knuth-Morris-Pratt 의 특징

  • 패턴내에 반복되는 문자열이 있을 경우, 가장 크게 반복되는 처음 문자열과 윈도우에서 가장 마지막까지 일치했던 부분을 일치시킴(이동)

    • BF에서는 윈도우 이동을 1씩 하지만, KMP에서는 그 이동크기를 최대화 함
    • 일치하지 않은 문자가 발생할 경우, 일치했던 부분을 텍스트에 맞추도록 윈도우 이동
  • 보통 BF보다 많이 빠르지는 않지만, 최악의 경우 길이 n의 텍스트 문자열에 대해 n번의 비교만 수행

• • 성능( text의 길이: n , pattern의 길이 m)

    • 시간 복잡도: O(2m+n)

  • • 전처리과정의 시간,공간 복잡도: O(m)
    • 검색시 시간 복잡도: O(n+m)

 

• Knuth-Morris-Pratt  설명

  • 텍스트와 패턴의 문자가 일치하지 않을 경우

  • • 틀린문자 이전에 텍스트와 패턴이 일치했던 문자열이 없을 경우: Step 1, 3

      • 윈도우를 1만큼 오른쪽으로 이동 (BF와 같다.)

    • 틀린문자 이전에 텍스트와 패턴이 일치했던 문자열이 있을 경우

    • • 일치했던 문자열과 패턴내에서 반복되는 문자열이 없는 경우: Step 2

        • 텍스트와 패턴이 일치한 문자열 만큼 이동
      • 일치했던 문자열과 패턴내에서 반복되는 문자열이 있는 경우: Step 4
      • • 윈도우의 일치했던 부분과 패턴의 일치했던 접두부분이 대응되도록 윈도우 이동

 

 

 

• 윈도우 이동위치 계산과 적용

  • 윈도우 이동 테이블(배열) = next

    • 틀린 부분의 패턴인덱스 -> 이동할 위치크기

 

• Knuth-Morris-Pratt 실행

  • 위의 예에서 특수한 경우, 0 대신 -1을 사용하여 shift 크기를 늘였음 (Step 2,3을 통합)

 

 

 

• Knuth-Morris-Pratt  소스

1. void preKmp(char *x, int m, int kmpNext[]) {
      int i, j;
   
      i = 0;
      j = kmpNext[0] = -1;
      while (i < m) {
         while (j > -1 && x[i] != x[j])
            j = kmpNext[j];
         i++;
         j++;
         if (x[i] == x[j])
            kmpNext[i] = kmpNext[j];
         else
            kmpNext[i] = j;
      }
   }
   
   
   void KMP(char *x, int m, char *y, int n) {
      int i, j, kmpNext[XSIZE];
   
      /* Preprocessing */
      preKmp(x, m, kmpNext);
   
      /* Searching */
      i = j = 0;
      while (j < n) {
         while (i > -1 && x[i] != y[j])
            i = kmpNext[i];
         i++;
         j++;
         if (i >= m) {
            OUTPUT(j - i);
            i = kmpNext[i];
         }
      }
   }