Matching from the right
Boyer Moore aligns the pattern with the text but compares characters from the rightmost position of the pattern backward. A mismatch near the right end can justify a large forward shift, which is why this method is fast in practice.
The bad character rule
When a text character fails to match, we look at where that character last appears in the pattern.
- If it appears earlier in the pattern, shift so those copies line up.
- If it never appears, shift the whole pattern past it in one jump.
This bad character heuristic exploits the alphabet to skip large regions.
The good suffix rule
The second heuristic uses the matched suffix. If the pattern partly matched before failing, we shift so another occurrence of that matched suffix, or a prefix that aligns with it, lines up with the text.
The algorithm takes the larger of the two suggested shifts.
Practical speed
On natural text with a large alphabet, the bad character rule alone produces big skips, and the average behavior is sublinear, often inspecting fewer characters than the text length.
Key idea
Boyer Moore scans the pattern right to left and combines bad character and good suffix rules to take big skips, often inspecting far fewer characters than the text holds.