Thuật toán Boyer-Moore (Good Suffix Heuristic)

Đây là phương pháp Good Suffix Heuristic của Boyer-Moore. Tạo bảng tiền xử lý suffix. Tìm kiếm từ ký tự cuối của pattern. Khi substring của text khớp với substring của pattern, tìm các occurrence khác của substring khớp đó. Có thể dịch chuyển để tìm prefix của pattern là suffix của text. Ngược lại, dịch chuyển toàn bộ độ 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

fullSuffixMatch(shiftArray, borderArray, pattern)

Begin
  n := pattern length
  i := n, j := n+1
  borderArray[i] := j
  while i > 0 do
    while j <= n AND pattern[i-1] ≠ pattern[j-1] do
      if shiftArray[j] = 0 then shiftArray[j] := j-i
      j := borderArray[j]
    done
    i--, j--; borderArray[i] := j
  done
End

partialSuffixMatch(shiftArray, borderArray, pattern)

Begin
  n := pattern length
  j := borderArray[0]
  for i := 0 to n-1 do
    if shiftArray[i] = 0 then shiftArray[i] := j
    if i = j then j := borderArray[j]
  done
End

searchPattern(text, pattern)

Begin
  patLen := pattern length, strLen := text length
  khởi tạo shiftArray = 0
  gọi fullSuffixMatch, partialSuffixMatch
  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 (tìm thấy match)
      shift += shiftArray[0]
    else shift += shiftArray[j+1]
  done
End

Ví dụ (C++)

#include <iostream>
#include <string>
using namespace std;

void fullSuffixMatch(int shift[], int border[], string pat) {
    int n = pat.size(), i = n, j = n+1;
    border[i] = j;
    while(i > 0) {
        while(j <= n && pat[i-1] != pat[j-1]) {
            if(shift[j] == 0) shift[j] = j-i;
            j = border[j];
        }
        i--; j--; border[i] = j;
    }
}

void partialSuffixMatch(int shift[], int border[], string pat) {
    int n = pat.size(), j = border[0];
    for(int i = 0; i < n; i++) {
        if(shift[i] == 0) shift[i] = j;
        if(i == j) j = border[j];
    }
}

void searchPattern(string text, string pat, int loc[], int *idx) {
    int m = pat.size(), n = text.size();
    int border[m+1], shift[m+1];
    for(int i=0;i<=m;i++) shift[i]=0;
    fullSuffixMatch(shift, border, pat);
    partialSuffixMatch(shift, border, pat);
    int s = 0;
    while(s <= n-m) {
        int j = m-1;
        while(j >= 0 && pat[j] == text[s+j]) j--;
        if(j < 0) { loc[++(*idx)] = s; s += shift[0]; }
        else s += shift[j+1];
    }
}

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

Đặc điểm: Boyer-Moore kết hợp Bad Character Rule và Good Suffix Rule, dịch chuyển lớn hơn so với naive search. Hiệu quả nhất cho pattern dài, alphabet lớn. Độ phức tạp tốt nhất O(n/m), trung bình O(n), xấu nhất O(nm).