Bad Character Heuristic (Quy tắc ký tự xấu) - Boyer-Moore

Bad Character Heuristic là một trong hai quy tắc của Boyer-Moore (còn lại là Good Suffix). Tìm "bad character" - ký tự của text không khớp với pattern tại vị trí so sánh. Khi mismatch, dịch pattern cho đến khi mismatch thành match, hoặc dịch qua bad character.

Độ phức tạp: O(n/m) tốt nhất, O(nm) xấu nhất (n=độ dài text, m=độ dài pattern).

Input và Output

Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern: "ABC"
Output: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Thuật toán

badCharacterHeuristic(pattern, badCharArray)

Begin
  n := pattern length
  for all entries of badCharArray do set -1 done
  for all chars of pattern do set last position in badCharArray done
End

searchPattern(pattern, text)

Begin
  patLen := pattern length, strLen := text length
  gọi badCharacterHeuristic
  shift := 0
  while shift <= strLen - patLen do
    j := patLen - 1
    while j >= 0 AND pattern[j] = text[shift+j] do j-- done
    if j < 0 then
      in shift (match)
      if shift+patLen < strLen then shift += patLen - badChar[text[shift+patLen]]
      else shift += 1
    else shift += max(1, j - badChar[text[shift+j]])
  done
End

Ví dụ (C++)

#include <iostream>
#define MAXCHAR 256
using namespace std;

int maximum(int a, int b) { return a>b?a:b; }

void badCharacterHeuristic(string pat, int badChar[MAXCHAR]) {
    int n = pat.size();
    for(int i=0;i= 0 && pat[j] == text[s+j]) j--;
        if(j < 0) {
            loc[++(*idx)] = s;
            if(s+m < n) s += m - badChar[text[s+m]];
            else s++;
        } else s += maximum(1, j - badChar[text[s+j]]);
    }
}

int main() {
    string text = "ABAAABCDBBABCDDEBCABC", pat = "ABC";
    int loc[text.size()], idx = -1;
    searchPattern(text, pat, loc, &idx);
    for(int i=0;i<=idx;i++) cout << "Pattern found at position: " << loc[i] << endl;
}

Kết quả

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Lưu ý: Bad Character Rule đơn giản hơn Good Suffix nhưng đôi khi dịch chuyển ít hơn. Kết hợp cả hai (original Boyer-Moore) cho hiệu năng tốt nhất.