Boyer-Moore법

• 브루트-포스법을 개선한 KMP법보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용되는 알고리즘
• 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.
• 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산하고 저장해야 하기 때문에 건너뛰기 표의 요소 개수는 Character.MAX_VALUE + 1 이다.
  • Character.MAX_VALUE는 Char형으로 나타낼 수 있는 문자 수

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

• 패턴에 들어 있지 않은 문자를 만난 경우
  1. 패턴을 옮길 크기는 n 이다. (현재 검사하고 있는 텍스트의 문자 위치로부터 다음에 검사할 패턴의 마지막 문자 위치가 n만큼 떨어질 수 있도록 패턴을 옮긴다.)
• 패턴에 들어 있는 문자를 만난 경우
  1. 패턴의 마지막 위치의 인덱스가 k이면 패턴을 옮길 크기는 n - k - 1 이다.
  2. 같은 문자가 패턴 안에 중복해서 들어 있지 않다면 패턴을 옮길 크기는 n 이다.

//Boyer-Moore법으로 문자열을 검색
 
static int bmMatch(String txt, String pat) {
    int pt;                                            //텍스트 커서
    int pp;                                            //패턴 커서
    int txtLen = txt.length();                        //텍스트의 문자열 길이
    int patLen = pat.length();                        //패턴의 문자열 길이
    int[] skip = new int[Character.MAX_VALUE + 1];    //건너뛰기 표
 
    //건너뛰기 표 만들기
    for (pt = 0; pt <= Character.MAX_VALUE; pt++) {
        skip[pt] = patLen;
    }
    for (pt = 0; pt < patLen - 1; pt++) {
        skip[pat.charAt(pt)] = patLen - pt - 1;    //pt == patLen - 1
    }
    
    // 검색
    while (pt < txtLen) {
        pp = patLen - 1;                //pat의 끝 문자에 주목
 
        while (txt.charAt(pt) == pat.charAt(pp)) {
            if (pp == 0)
                return pt;    // 검색 성공
            pp--;
            pt--;
        }
        pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
    }
    return -1;
}