[박혜웅] Boyer-Moore

•  Boyer-Moore의 특징

  • 윈도우는 왼쪽에서 오른쪽으로 이동하며, 패턴내에서 오른쪽에서 왼쪽으로 검사한다.
  • 문자열이 불일치 할 때 대상 text에서 다음 비교를 위해서 이동할 위치를 최대화한 알고리즘이다.

  • 성능

    • 전처리시 공간복잡도 : O(m+)
    • 검색시 시간복잡도: O(mn)
    • 최악의 경우 비교회수: 3n
    • 최상의 경우 비교회수: O(n/m)

 

 

• Boyer-Moore의 설명

  • 일치하지 않는 문자가 나왔을 때  good-suffix shift 또는 bad-character shit 중 큰 값으로 윈도우를 이동한다.

  •  good-suffix shift

    • 텍스트와 일치하는 문자열이 패턴에 2개이상 존재하는 경우
    •  
    • 텍스트와 일치하는 문자열이 패턴에 1개만 존재하는 경우

    •  

       

  • bad-character shit

  • • 텍스트와 다른 문자가 패턴에 2개이상 존재하는 경우
    • 
      
    • 텍스트와 다른 문자가 패턴에 1개만 존재하는 경우
    •  

 

 

• Boyer-Moore의 실행

 http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140

• 
  

 

• Boyer-Moore의 소스

1. void preBmBc(char *x, int m, int bmBc[]) {
      int i;
   
      for (i = 0; i < ASIZE; ++i)
         bmBc[i] = m;
      for (i = 0; i < m - 1; ++i)
         bmBc[x[i]] = m - i - 1;
   }
   
   
   void suffixes(char *x, int m, int *suff) {
      int f, g, i;
   
      suff[m - 1] = m;
      g = m - 1;
      for (i = m - 2; i >= 0; --i) {
         if (i > g && suff[i + m - 1 - f] < i - g)
            suff[i] = suff[i + m - 1 - f];
         else {
            if (i < g)
               g = i;
            f = i;
            while (g >= 0 && x[g] == x[g + m - 1 - f])
               --g;
            suff[i] = f - g;
         }
      }
   }
   
   void preBmGs(char *x, int m, int bmGs[]) {
      int i, j, suff[XSIZE];
   
      suffixes(x, m, suff);
   
      for (i = 0; i < m; ++i)
         bmGs[i] = m;
      j = 0;
      for (i = m - 1; i >= 0; --i)
         if (suff[i] == i + 1)
            for (; j < m - 1 - i; ++j)
               if (bmGs[j] == m)
                  bmGs[j] = m - 1 - i;
      for (i = 0; i <= m - 2; ++i)
         bmGs[m - 1 - suff[i]] = m - 1 - i;
   }
   
   
   void BM(char *x, int m, char *y, int n) {
      int i, j, bmGs[XSIZE], bmBc[ASIZE];
   
      /* Preprocessing */
      preBmGs(x, m, bmGs);
      preBmBc(x, m, bmBc);
   
      /* Searching */
      j = 0;
      while (j <= n - m) {
         for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
         if (i < 0) {
            OUTPUT(j);
            j += bmGs[0];
         }
         else
            j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
      }
   }