본문 바로가기

자료구조 & 알고리즘/문자열 매칭 알고리즘

[박혜웅] 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];
          }
       }
    }

 

'자료구조 & 알고리즘 > 문자열 매칭 알고리즘' 카테고리의 다른 글

[박혜웅] Shift-Or  (0) 2010.03.27
[박혜웅] Karp-Rabin  (0) 2010.03.27
[박혜웅] Brute Force(BF)  (0) 2010.03.27
[박혜웅] Boyer-Moore-Horspool  (0) 2010.03.27
[박혜웅] Boyer-Moore  (0) 2010.03.27