1. One-Liner
Boyer–Moore matches the pattern from the right and, on mismatch, shifts the pattern using bad-character (and often good-suffix) rules to skip large chunks of the text.
2. The Problem It Solves
Speed up substring search when the alphabet is large and mismatches occur early — typical grep-style scanning can be sublinear in practice on natural language.
3. The Core Idea
If the text character under the pattern’s right end does not match, slide the pattern so that a matching character aligns (bad-character rule). The good-suffix rule uses already-matched suffix structure similarly to KMP borders but from the right.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1 | Precompute last occurrence of each character in P (bad-character table). |
| 2 | Align P at start of a window; compare P[m-1] with T[...] leftward. |
| 3 | On mismatch at (i, j), shift by max(1, j - last[T[i]]) (simplified bad-character). |
| 4 | Optional: add good-suffix shifts for full algorithm; Galil rule for linearity guarantees in variants. |
5. Dry Run Example
T = "HERE IS A SIMPLE EXAMPLE", P = "EXAMPLE" — right-to-left match fails fast on wrong letters; shifts jump past impossible columns.
6. Key Properties
| Property | Value |
|---|---|
| Best case | O(n/m) comparisons (very sparse) |
| Worst case | O(n·m) naive BM; improved variants O(n+m) |
| Extra space | O(alphabet + m) with full tables |
7. Where It Is Used
| Domain | Use |
|---|---|
| GNU grep | Classic BM-style engines |
| Editors | Fast search in buffers |
| Security | Signature scanners (combined with other algos) |
8. Interview Tips
Explain why right-to-left helps; give bad-character formula. Mention good-suffix as the harder table. Compare average case vs KMP worst-case guarantees.
9. Comparison with Other Algorithms
| Algorithm | Scan direction | Typical |
|---|---|---|
| KMP | Left–right | Guaranteed linear |
| Boyer–Moore | Right–left | Often faster in practice |
| Sunday/Horspool | Simpler shifts | Easier implementations |
10. Complexity
| Metric | Value |
|---|---|
| Preprocess | O(m + σ) for basic tables |
| Search (classic) | O(n·m) worst; sublinear many inputs |
Implementation Example (PYTHON)
def boyer_moore_bad_char(pat):
return {c: i for i, c in enumerate(pat)}
def boyer_moore_search(text, pat):
n, m = len(text), len(pat)
if m == 0:
return list(range(n + 1))
last = boyer_moore_bad_char(pat)
res = []
s = 0
while s <= n - m:
j = m - 1
while j >= 0 and text[s + j] == pat[j]:
j -= 1
if j < 0:
res.append(s)
s += 1
else:
ch = text[s + j]
k = last.get(ch, -1)
s += max(1, j - k)
return res