Boyer-Moore
Compare from the right; on a mismatch slide so the pattern's last copy of the bad character lines up, or past it.
Shift 0: compare from the right. 0 agree, then text 'b' at offset 3 differs from 'a'. The rightmost 'b' in the pattern is at index 1, so slide 3 - 1 = 2 to line them up.
What you will see
Comparison runs right to left; a mismatch jumps the pattern several cells at once.
Cost
| Best | O(n / m) |
|---|---|
| Average | O(n) |
| Worst | O(n * m) |
| Space | O(alphabet + m) |
Worst case O(n + m) with the Galil rule.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Text and pattern cells announce index and character; each step announces the aligned positions, the comparison result and the shift.
Reduced motion: The pattern row snaps to its new alignment with a crossfade instead of sliding.
Before this
Related
Taught by the same lesson
String Matching covers these too, in the same run.