string-search • Advanced

Boyer-Moore Search: Bad Character & Good Suffix Rules

Boyer-Moore searches strings by matching pattern characters right-to-left, skipping up to M characters in a single jump to achieve sublinear O(N/M) average search speed (used in GNU grep).

Intuitive Mental Model

Reading From Right to Left: When looking for "ELEPHANT" in text, you check the 'T' first. If you see 'Z', you immediately know "ELEPHANT" cannot exist anywhere in those 8 characters and skip past all 8 letters in 1 jump.

C / TypeScript ImplementationHardware & Algorithmic Standard

// Boyer-Moore Bad Character Shift Table:
function buildBadCharTable(pattern: string): Map<string, number> {
  const table = new Map<string, number>();
  for (let i = 0; i < pattern.length; i++) {
    table.set(pattern[i], i);
  }
  return table;
}

Key Architectural Takeaways

•Sublinear Average Time: O(N / M) average search speed on large alphabets.
•Industry Standard: The algorithm behind GNU grep and code editor search engines.

Common Coding Mistake

Assuming Boyer-Moore is always faster on small alphabets (e.g. binary strings where bad character shifts are minimal).

Optimal Solution

Use KMP or Bitap on small binary alphabets.

Next: Trie (Prefix Tree) & Autocomplete Dictionaries