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

Boyer-Moore: Combined Algorithm

Combine both Boyer-Moore heuristics to achieve sublinear average-case performance, the fastest practical string search.

Boyer-Moore: Combined Algorithm

What you'll learn: How combining Boyer-Moore's Bad Character and Good Suffix heuristics creates the fastest practical string search algorithm.


The Power of Two Heuristics

You've learned two clever ways Boyer-Moore can skip ahead when mismatches occur. Now comes the magic: use both rules together and take the maximum skip.

When a mismatch happens at position i in the pattern:

  1. Calculate the skip distance using the Bad Character Rule (based on the mismatched text character)
  2. Calculate the skip distance using the Good Suffix Rule (based on the already-matched suffix)
  3. Shift by whichever suggests a larger jump

Why This Works So Well

Think of it like having two expert advisors. One studies the "bad" character that caused the mismatch; the other analyzes the "good" suffix you already matched. You take the more aggressive advice.

In many real-world scenarios (English text, DNA sequences, code), patterns often mismatch on characters that don't appear elsewhere in the pattern. The Bad Character Rule excels here, sometimes skipping the entire pattern length. When you have repetitive patterns, the Good Suffix Rule prevents unnecessary comparisons.

Sublinear Average Case

By combining both heuristics, Boyer-Moore achieves O(n/m) average-case time on random text, where n is text length and m is pattern length. You examine fewer characters than the text contains! This happens because large skips mean you never look at most characters.

Worst case: Still O(n·m), but extremely rare in practice.

Key Takeaway: Boyer-Moore combines Bad Character and Good Suffix rules by taking the maximum skip at each mismatch, achieving sublinear average-case performance and making it the fastest practical string search algorithm for typical data.