320. What is the key idea behind Boyer-Moore string search?
HardString algorithms
Show model answer
Boyer-Moore aligns the pattern with the text but compares from the pattern’s right end. On a mismatch it shifts using two precomputed heuristics and takes the larger shift. The bad-character rule moves the pattern so the mismatched text character lines up with its last occurrence in the pattern (or past it entirely if absent). The good-suffix rule moves it so the already matched suffix lines up with another occurrence of that suffix, or with a matching prefix.
Because a mismatch on a character absent from the pattern can skip m positions at once, Boyer-Moore is sublinear on typical text, approaching O(n/m) comparisons, and is the basis of many fast "find" tools. With only the bad-character rule (Horspool’s simplification) the worst case is O(nm); the full algorithm with the Galil rule is O(n + m). Preprocessing costs O(m + σ).