Course contentsShow
← Computer Science
Lesson 836 of 2,87219. Searching and SelectionFree lesson

Boyer-Moore: Bad Character Rule

Learn Boyer-Moore's bad character heuristic that shifts the pattern based on mismatched characters from right to left.

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:

  1. The rightmost character mismatches—let's say the text has 'Z' where you expected 'E'
  2. You look: does 'Z' appear anywhere in "EXAMPLE"? No!
  3. 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.