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:
- Does this matched suffix appear elsewhere in the pattern?
- 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.