문자열 검색: Boyer-Moore법

• Boyer-Moore법 -> KMP법보다 효율이 더 좋음 !

패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면

미리 준비한 표에 따라 패턴을 옮길 크기를 정함

 

• 건너뛰기 표

패턴의 문자열의 길이가 n일 때 옮길 크기는 다음과 같이 결정:

1. 패턴에 들어 있지 않은 문자를 만난 경우: n

2. 패턴에 들어 있는 문자를 만난 경우

    2-1. 해당 문자가 패턴 안에 중복되지 않으면서 마지막에 있는 경우: n

    2-2. 그 외의 패턴의 마지막 문자의 인덱스가 k일 때:  n - k - 1

 

패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산해야 하므로 건너뛰기 표의 요소 개수는 UCHAR_MAX + 1

(UCHAR_MAX: 표현할 수 있는 문자의 개수로 <limits.h>에 객체 형식 매크로로 정의되어 있음)

 

• Boyer-Moore법 알고리즘

#include <stdio.h>
#include <string.h>
#include <limits.h>

int bm_match(const char txt[], const char pat[]){
  int pt; //txt 커서
  int pp; //pat 커서
  int txt_len = strlen(txt);
  int pat_len = strlen(pat);
  int skip[UCHAR_MAX + 1];

  //건너뛰기 표 만들기
  for(pt = 0; pt <= UCHAR_MAX; pt++) skip[pt] = pat_len;
  for(pt = 0; pt < pat_len - 1; pt++) skip[pat[pt]] = pat_len - pt -1;

  //검색
  while(pt < txt_len){ //이 시점에서 pt = pat_len-1;
    pp = pat_len - 1; //패턴의 마지막 문자부터 비교
    while(txt[pt] == pat[pp]){
      if(pp==0) return pt; //모두 같으면 리턴
      pp--;
      pt--;
    }
    pt += (skip[txt[pt]] > pat_len - pp) ? skip[txt[pt]] : pat_len - pp;
    /*skip[txt[pt]]가 더 작은 경우는 패턴이 있던 자리보다 뒤로 가야 하는 경우
    (pat_len - pp)만큼 pt를 옮긴다는 것은 패턴을 한 칸 뒤로 민다는 것(최소 움직임)*/
  }
  return -1;
}

int main(void){
  int idx;
  char s1[256];
  char s2[256];

  puts("Boyer-Moore법");
  printf("텍스트 : ");
  scanf("%s",s1);

  printf("패턴 : ");
  scanf("%s",s2);

  idx = bm_match(s1, s2);

  if(idx==-1) puts("텍스트에 패턴이 없습니다.");
  else printf("%d번째 문자부터 match합니다.\n", idx + 1);

  return 0;
}

 

시간 복잡도: 텍스트의 문자 개수가 n이고, 패턴의 문자 개수가 m일 때 worst - O(n), avg - O(n/m)