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

Boyer-Moore: Good Suffix Rule

Understand the good suffix heuristic in Boyer-Moore that enables larger shifts when a suffix matches but mismatch occurs.

Boyer-Moore: Good Suffix Rule

You'll learn how the good suffix heuristic in Boyer-Moore enables smarter pattern shifts by leveraging matched suffixes when a mismatch occurs.


What's the Core Idea?

When you've already matched part of the pattern (a suffix) but then hit a mismatch, the good suffix rule tells you: "I know this suffix matched—where else could it appear in my pattern?" This lets you shift the pattern intelligently, skipping positions where alignment is impossible.

Unlike the bad character rule (which looks at the mismatched text character), the good suffix rule looks at the matched portion of your pattern and asks:

  1. Does this matched suffix appear elsewhere in the pattern?
  2. Does a prefix of the pattern match a suffix of this matched portion?

Based on the answer, you can shift the pattern much further than just one position.


How It Works

Imagine searching for pattern "EXAMPLE" in text. You scan right-to-left and match "PLE" but mismatch at 'M'. The good suffix rule asks:

  • "Can I find 'PLE' earlier in my pattern?" If yes, align it there.
  • "If not, is there a prefix of 'EXAMPLE' that matches a suffix of 'PLE'?" Maybe "E" appears at the start?

If neither condition holds, you can safely shift the pattern past the entire matched portion—saving many comparisons.

The rule is precomputed in a table during preprocessing, so lookups during search are instant.


Why It Matters

The good suffix rule complements the bad character rule. Together, they enable Boyer-Moore to shift by the maximum of both heuristics, often jumping over large chunks of text. This is why Boyer-Moore can achieve sublinear time in practice.

Key Takeaway:
The good suffix rule shifts the pattern based on where matched suffixes reappear in the pattern itself, enabling large, intelligent jumps that exploit information from successful partial matches.