본문 바로가기

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

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