Boyer-Moore: Bad Character Rule
What you'll learn: How Boyer-Moore uses mismatched characters to skip large portions of text intelligently.
The Core Idea
The Boyer-Moore algorithm searches for a pattern by comparing characters from right to left (unlike the naive approach that goes left to right). When a mismatch occurs, the bad character rule tells us how far we can safely shift the pattern forward without missing any potential matches.
The key insight: when you encounter a character in the text that doesn't match the pattern, check if that "bad character" appears elsewhere in your pattern. This tells you how far you can slide the pattern.
How It Works
Imagine searching for the pattern "EXAMPLE" in some text. You align it and start checking from the right:
- The rightmost character mismatches—let's say the text has
'Z'where you expected'E' - You look: does
'Z'appear anywhere in"EXAMPLE"? No! - You can skip the entire pattern length because no alignment overlapping this position could possibly match
If the bad character does appear in the pattern, you shift the pattern just enough to align that character's rightmost occurrence with the mismatched position in the text.
The Preprocessing Step
Before searching, you build a bad character table: for each possible character, record its rightmost position in the pattern (or -1 if absent). During search, when character c causes a mismatch at text position i, you calculate the shift using this table.
This simple rule often lets you skip many characters at once—especially effective when the alphabet is large or the pattern doesn't match.
Key Takeaway: The bad character rule shifts the pattern based on where (or if) the mismatched text character appears in the pattern, enabling large jumps forward when comparing right-to-left.