[박혜웅] Boyer-Moore-Horspool

• Boyer-Moore-Horspool의 특징

  • Boyer-Moore의 2가지 shift 방법중 bad-character shift 만 이용한다.

    • bad-character shift 는 알파벳이 패턴의 길이보다 클 때, 유용하다.

 

•  Boyer-Moore-Horspool 의 개념

  • Boyer-Moore의 개념과 동일하며, good-suffix shift 만 사용하지 않는다.

 

• Boyer-Moore-Horspool 의 실행

 

 

• Boyer-Moore-Horspool 의 소스

1. void HORSPOOL(char *x, int m, char *y, int n) {
      int j, bmBc[ASIZE];
      char c;
   
      /* Preprocessing */
      preBmBc(x, m, bmBc);
   
      /* Searching */
      j = 0;
      while (j <= n - m) {
         c = y[j + m - 1];
         if (x[m - 1] == c && memcmp(x, y + j, m - 1) == 0)
            OUTPUT(j);
         j += bmBc[c];
      }
   }