Boyer-Moore

Read FEWER than n characters. The grep algorithm. Scan right-to-left; skip forward. Longer pattern → faster search.

The bad-character rule

• Align the pattern; compare from its RIGHT end backward
• Mismatch on text char c? Slide so c's rightmost spot in the pattern lines up
• c not in the pattern at all? Leap the WHOLE pattern length past it
• Characters the jump skips are never examined

Watch it leap

'z' and 'y' aren't in abcd → full-length leaps, skipping unread chars. Blue = comparing · green = matched suffix · red = mismatch → jump.

Longer pattern, fewer examinations

KMP: flat ~n (reads everything). Boyer-Moore: DESCENDS. m=64 → 24× fewer examinations.

The catches

• Bad-char alone: O(n·m) worst case → add the good-suffix rule (full BM)
• Big win on LARGE alphabets + LONG patterns; small alphabet → KMP competitive
• Horspool variant (bad-char only) is what grep-family tools ship
• Always max(1, shift) or it stalls

Takeaway

Opportunistic (skip) vs steady (KMP reads all) — know your regime. Real text, big alphabet → Boyer-Moore. That's why grep flies. Single-pattern trilogy done. Next: suffix arrays index the TEXT.