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.
String Matching: Boyer-Moore jumps by the bad character
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.
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.
Before this
Taught by the same lesson
String Matching covers these too, in the same run.