Bad Character Heuristic (ฮิวริสติกตัวอักษรผิด) - Boyer-Moore

Bad Character Heuristic เป็นหนึ่งใน 2 Heuristics ของ Boyer-Moore Algorithm (อีกคือ Good Suffix) ใช้ตารางเก็บ ตำแหน่งสุดท้าย (Rightmost occurrence) ของแต่ละตัวอักษรใน Pattern

แนวคิดการทำงาน

1. สร้างตาราง badChar[256] เก็บ index สุดท้ายของแต่ละ ASCII character ใน Pattern (ไม่พบ = -1)
2. จับคู่ Pattern กับ Text จากขวาไปซ้าย
3. เมื่อพบ Mismatch ที่ตำแหน่ง j ของ Pattern (ตัวอักษร c = text[shift+j]):
4. เลื่อน Pattern ให้ c ใน Pattern ตรงกับ c ใน Text: shift = max(1, j - badChar[c])
5. ถ้า Match สมบูรณ์: เลื่อน shift += pattern.length (หรือใช้ Good Suffix)

ตัวอย่างข้อมูล

Text:    ABAAABCDBBABCDDEBCABC
Pattern: ABC

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

อัลกอริทึม (Pseudocode)

badCharacterHeuristic(pattern, badChar[256])
  for i = 0 to 255: badChar[i] = -1
  for i = 0 to pattern.length-1:
    badChar[pattern[i]] = i  // เก็บตำแหน่งสุดท้าย

searchPattern(text, pattern)
  badCharacterHeuristic(pattern, badChar)
  shift = 0
  while shift <= text.length - pattern.length:
    j = pattern.length - 1
    while j >= 0 AND pattern[j] == text[shift+j]: j--
    if j < 0:
      report match at shift
      if shift + pattern.length < text.length:
        shift += pattern.length - badChar[text[shift + pattern.length]]
      else:
        shift += 1
    else:
      shift += max(1, j - badChar[text[shift+j]])

ตัวอย่างโค้ด C++

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

#define MAXCHAR 256

void badCharacterHeuristic(string pattern, int badChar[MAXCHAR]) {
    fill(badChar, badChar + MAXCHAR, -1);
    for (int i = 0; i < pattern.size(); i++)
        badChar[(int)pattern[i]] = i;
}

void searchPattern(string text, string pattern) {
    int n = pattern.size(), m = text.size();
    int badChar[MAXCHAR];
    badCharacterHeuristic(pattern, badChar);

    int shift = 0;
    while (shift <= m - n) {
        int j = n - 1;
        while (j >= 0 && pattern[j] == text[shift + j]) j--;

        if (j < 0) {
            cout << "Pattern found at position: " << shift << endl;
            if (shift + n < m)
                shift += n - badChar[text[shift + n]];
            else
                shift += 1;
        } else {
            shift += max(1, j - badChar[text[shift + j]]);
        }
    }
}

int main() {
    string text = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    searchPattern(text, pattern);
}

ความซับซ้อน

• Preprocessing: O(m + σ) โดย σ = alphabet size (256)
• Searching: O(n/m) Best case, O(n·m) Worst case
• Space: O(σ)

ข้อสังเกต

• Bad Character ใช้งานง่าย ประสิทธิภาพดีกับ Alphabet ใหญ่
• Good Suffix จำเป็นต้องใช้ร่วมเพื่อประสิทธิภาพสูงสุด
• รวมกัน: shift = max(badCharShift, goodSuffixShift)