Boyer-Moore String Search — When Bad Character Alone Fails

Open a terminal and run: grep -c 'the' /usr/share/dict/words. Grep finds all matches faster than you can think about it. The reason: Boyer-Moore (specifically Boyer-Moore-Horspool). The longer your search pattern, the faster it runs — counterintuitively, Boyer-Moore gets faster as patterns get longer because it skips more characters per comparison.

This sub-linear behaviour is the key insight. KMP guarantees O(n+m) worst case. Boyer-Moore achieves O(n/m) in practice on natural language text — for a 10-character pattern, it examines roughly 1 in 10 characters in the text. This is why Boyer-Moore is the default in text editors, grep, and most real-world text search implementations despite KMP being theoretically simpler.

Right-to-Left Matching

Boyer-Moore aligns the pattern at the left of the text and compares right-to-left — from the last character of the pattern backward. When it finds a mismatch, it applies whichever of the two heuristics gives the larger skip.

This right-to-left comparison is key: when we find a mismatch at pattern position j (text position i+j), we know nothing about text[i+j+1..i+m-1] — but we know the characters to the right are already matched. This asymmetry is what makes skipping possible.

The Bad Character Heuristic

When a mismatch occurs at text position i+j (pattern position j), look at the mismatched text character c = text[i+j]. The bad character rule says: shift the pattern right so that the rightmost occurrence of c in the pattern aligns with position i+j.

If c doesn't appear in the pattern at all, shift the entire pattern past position i+j — a shift of j+1. If c appears in the pattern to the left of j, shift to align the rightmost such occurrence. If c only appears to the right of j, the bad character rule gives a negative shift — ignore it (use 0 or the good suffix rule).

def bad_char_table(pattern: str) -> dict[str, int]:
    """
    Returns last occurrence index of each character in pattern.
    If char not in pattern, returns -1 (handled at call site).
    """
    table = {}
    for i, ch in enumerate(pattern):
        table[ch] = i
    return table

pattern = 'ABCBAB'
table = bad_char_table(pattern)
print(table)  # {'A': 4, 'B': 5, 'C': 2}

Boyer-Moore with Bad Character Only (Simplified)

A simplified version using only the bad character heuristic is called Boyer-Moore-Horspool and is often used in practice for its simplicity. It's the default in many text editors and grep implementations because it's fast enough for general text. The trade-off is worst-case O(nm) on repetitive inputs.

def boyer_moore_horspool(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []

    # Build bad character table
    bad_char = {ch: i for i, ch in enumerate(pattern)}
    matches = []
    s = 0  # shift of the pattern w.r.t. text

    while s <= n - m:
        j = m - 1  # start from rightmost character

        # Move left while characters match
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1

        if j < 0:
            matches.append(s)  # full match found
            # Shift by 1 (or use good suffix for full Boyer-Moore)
            s += 1
        else:
            # Bad character shift
            bc = bad_char.get(text[s + j], -1)
            s += max(1, j - bc)

    return matches

print(boyer_moore_horspool('ABAAABCD', 'ABC'))      # [4]
print(boyer_moore_horspool('AABCAABXAAB', 'AABX'))  # [4]

The Good Suffix Heuristic

When a mismatch occurs after matching t characters (the 'good suffix'), the good suffix rule shifts the pattern to align the next occurrence of that suffix. This is more complex to implement but provides better worst-case guarantees.

For most interview purposes, the bad-character-only version (Horspool) is sufficient to explain and implement. But in production, if you can't guarantee input randomness, implement the good suffix rule.

Worked Example: Tracing Shifts on a Short Text

Text: AAABBBCCCABC Pattern: ABC

Step 1: Align at position 0. Compare right-to-left: text[2]='A' vs pattern[2]='C' → mismatch. Bad char 'A' is at index 0 in pattern. Shift = max(1, 2-0) = 2. Move to s=2.

Step 2: s=2. Compare right-to-left: text[4]='B' vs pattern[2]='C' → mismatch. Bad char 'B' at index 1. Shift = max(1, 2-1) = 1. Move to s=3.

Step 3: s=3. Compare: text[5]='B' vs 'C' → mismatch. Bad char 'B' at 1. Shift=1. s=4.

... continues until s=9 where ABC matches. Total: only examined ~8 positions instead of 30 naive comparisons.

This demonstrates the sub-linear behaviour: for a 3-character pattern, we skip 2 out of every 3 characters on average.