AlgoScope

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 algorithms, algorithm, advanced
Bad character b, slide 2.txtpatacabbcabcaabcaabcab > a

String Matching: Boyer-Moore jumps by the bad character

Decision, step 2 of 10

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.

How string matching works

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.

Taught by the same lesson

String Matching covers these too, in the same run.