Boyer-Moore

What this chapter covers

KMP and Rabin-Karp both read every character of the text. Boyer-Moore reads fewer than the text is long — it's the rare algorithm that's genuinely sublinear, examining a fraction of the characters it searches, and the counterintuitive consequence is that a longer pattern makes it faster. It pulls this off with two ideas: it aligns the pattern against the text and compares from the right end backward, and on a mismatch it uses what it just saw to slide the pattern forward by a provably-safe jump — often leaping over many text characters without ever looking at them. When the mismatched character doesn't appear in the pattern at all, Boyer-Moore skips the pattern's entire length in one move. This chapter builds the core bad-character rule, watches the pattern leap across a text, and measures the payoff: on a long pattern it examined 24 times fewer characters than KMP. This is the engine inside grep.

A bit of history

Robert Boyer and J Strother Moore published the algorithm in 1977 — the same year as KMP, a remarkable year for string matching — while at the Stanford Research Institute and SRI. Their paper made a claim that sounded impossible: a search algorithm whose running time decreases as the pattern gets longer, because a longer pattern allows bigger skips. That turned the naive intuition (more pattern, more work) on its head. The full algorithm combines two shift rules — the bad-character rule this chapter builds and a subtler "good-suffix" rule — and the worst-case analysis took years to settle: the original could be $O(n \cdot m)$ in adversarial cases, and it was Zvi Galil in 1979, then others, who added refinements guaranteeing linear worst-case time. But the practical version, especially the simplified Boyer-Moore-Horspool variant, became the default for real text search because on ordinary text over a large alphabet it's simply the fastest thing going. When you run grep, a Boyer-Moore descendant is doing the work.

The intuition

Line the pattern up with the start of the text, but compare from the right. Look at the text character under the pattern's last character. If they match, step left and compare the next pair; if you match all the way to the pattern's start, you've found an occurrence. But usually you'll hit a mismatch quickly, and here's where the magic happens. Suppose the mismatched text character is c. Ask: where does c appear in the pattern? If it appears somewhere, slide the pattern right so that occurrence of c lines up under this text c — there's no point trying alignments that wouldn't put a matching character there. If c doesn't appear in the pattern at all, then no alignment overlapping this c can possibly match, so slide the pattern entirely past it — a jump of the full pattern length.

That's the bad-character rule, and its power grows with the alphabet and the pattern length. On English text or DNA, most characters you probe won't be at the right spot in the pattern, so most windows are dismissed after a single comparison and a big jump. The pattern skates across the text touching maybe one character in every m. Compare this to KMP, which patiently reads every text character left to right: KMP never skips, so it examines all n. Boyer-Moore skips aggressively, so it examines $\approx n/m$ on good inputs. The right-to-left scan is what makes the skipping possible — by checking the end of the pattern first, a single mismatch tells you about an entire window's worth of alignments.

Complexity: how it scales

Boyer-Moore's best case is $O(n/m)$ — when the pattern's last character keeps mismatching against text characters absent from the pattern, every probe triggers a full-length skip, so it touches only about $n/m$ characters. Its average on random text over an alphabet of size $\sigma$ is sublinear, roughly $O(n/\min(m, \sigma))$. The bad-character rule alone has an $O(n \cdot m)$ worst case (on adversarial repetitive input, like KMP's nemesis but for skipping); adding the good-suffix rule, or using the Galil refinement, restores a linear worst case. The bad-character table costs $O(\sigma + m)$ to build. The face-off shows the signature behavior directly — characters examined as the pattern lengthens, Boyer-Moore against KMP:

Look at the two lines. KMP's is flat — it examines about 100,000 characters (the whole text) no matter how long the pattern is, because it never skips. Boyer-Moore's line descends: the longer the pattern, the bigger its skips, the fewer characters it looks at. At pattern length 64 it examined about 4,200 characters against KMP's 100,000 — 24 times fewer, and still dropping. This is the plot that captures why Boyer-Moore is special: it's the only major search algorithm where the work goes down as the problem's pattern grows, because its whole strategy is to use the pattern's length as a license to skip. On a large alphabet, that makes it the practical winner for real text search.

What it's good at, what it isn't

Boyer-Moore is the right tool for searching text over a reasonably large alphabet — natural language, source code, general byte streams — which is most everyday search. Its sublinear average makes it the default in grep, text editors' find, and language runtimes' substring routines. The longer the pattern, the more it wins, so it excels at finding long fixed strings. And it needs no preprocessing of the text (only the small pattern), so it's ideal for searching large files or streams you can't index in advance.

Where it's less suited is small alphabets, where the bad-character rule loses its punch: on binary data or DNA (alphabet of 2 or 4), the mismatched character is almost always somewhere in the pattern, so skips are short and Boyer-Moore's advantage over KMP shrinks (the good-suffix rule helps here, and specialized algorithms exist). Its bad-character-only form has a quadratic worst case, so adversarial or untrusted input calls for the full version or a linear-guarantee algorithm. For multiple patterns, Aho-Corasick (next chapter) is better; for streaming where you can't look ahead-and-back freely, KMP's strictly-forward scan fits better. And, as always, for a one-off search in application code you'd just call str.find — which is itself a Boyer-Moore relative under the hood.

The data, or the inputs

The face-off searches a 100,000-character random text over the 26-letter alphabet for patterns of growing length, counting how many text characters Boyer-Moore and KMP each examine — the direct measure of skipping. Correctness is checked on three thousand random text/pattern pairs across alphabets from size 2 to 26: Boyer-Moore's matches must exactly equal Python's built-in str.find. The animation runs Boyer-Moore searching for abcd in zzzzabcdyabcd, chosen so the mismatched characters (z, y) are absent from the pattern and trigger full-length leaps you can watch.

Build it, one function at a time

The bad-character table — the rightmost occurrence of each character in the pattern:

def last_occurrence(pattern):
    """For each character, the index of its RIGHTMOST occurrence in the pattern. This is the
    bad-character table: when a mismatch happens at a text character c, this tells us where c
    could line up inside the pattern, so we can slide the pattern to align them (or leap past
    c entirely if it never appears)."""
    last = {}
    for i, ch in enumerate(pattern):
        last[ch] = i                             # later positions overwrite earlier → rightmost wins
    return last

And the search — right-to-left comparison, forward skip on mismatch:

def boyer_moore(text, pattern):
    """Find every occurrence of `pattern` in `text` using the bad-character rule. Align the
    pattern, compare right-to-left; on a mismatch at text character c, shift the pattern forward
    so c's rightmost occurrence in the pattern lines up under it (never less than 1). Characters
    the shift jumps over are never examined — the source of the sublinear behavior. Returns
    (matches, examined) where `examined` counts text characters actually looked at."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    last = last_occurrence(pattern)
    matches, examined = [], 0
    i = 0                                        # index in text where the pattern's left end sits
    while i <= n - m:
        j = m - 1                                # start comparing from the RIGHT end of the pattern
        while j >= 0:
            examined += 1
            if text[i + j] != pattern[j]:
                break
            j -= 1
        if j < 0:                                # ran off the left end → full match
            matches.append(i)
            i += 1                               # shift by one to find overlapping matches
        else:
            c = text[i + j]                      # the mismatching text character
            shift = j - last.get(c, -1)          # align c with its rightmost spot in the pattern
            i += max(1, shift)                   # never stall; skip the chars in between unexamined
    return matches, examined

Watch it work

Here's Boyer-Moore searching for abcd (bottom) in zzzzabcdyabcd (top). Watch the very first move: the pattern aligns at the start, and the first comparison is at the pattern's right end — text position 3, a z. Since z doesn't appear in abcd at all, no alignment overlapping that z could ever match, so the pattern leaps its entire length forward, skipping positions 0–3 without ever examining them. It lands exactly on abcd and matches, right-to-left, in four comparisons. Then the lone y (also absent from the pattern) triggers another full leap to the second abcd. The pattern skates across the text, touching only a handful of its thirteen characters — blue is the character being compared, green the matched suffix, red a mismatch that launches a jump:

The complete code

The from-scratch tab is Boyer-Moore with the bad-character rule; the library tab is KMP, the every-character contrast used to check correctness and count examinations in the face-off, plus the str.find reference. Flip between them to see the two philosophies — read everything (KMP) versus skip aggressively (Boyer-Moore).

"""Boyer-Moore — the substring search that reads FEWER than n characters. KMP and Rabin-Karp
both examine every character of the text. Boyer-Moore examines a fraction of them, which is
why it (and its variants) sit inside grep, and why the counterintuitive rule holds: the LONGER
the pattern, the FASTER the search.

The trick is two ideas working together. First, it aligns the pattern with the text and compares
RIGHT TO LEFT — from the end of the pattern backward. Second, on a mismatch it uses what it just
saw to slide the pattern FORWARD by as much as is provably safe, often skipping over many text
characters without ever looking at them. This chapter builds the core "bad-character rule": when
a text character doesn't match, look at where (if anywhere) that character appears in the pattern,
and shift so those line up — or, if the character isn't in the pattern at all, leap the whole
pattern length past it. On a large alphabet that means most windows are dismissed after a single
comparison, and the search runs in sublinear time on average.
"""


# region: bad_char
def last_occurrence(pattern):
    """For each character, the index of its RIGHTMOST occurrence in the pattern. This is the
    bad-character table: when a mismatch happens at a text character c, this tells us where c
    could line up inside the pattern, so we can slide the pattern to align them (or leap past
    c entirely if it never appears)."""
    last = {}
    for i, ch in enumerate(pattern):
        last[ch] = i                             # later positions overwrite earlier → rightmost wins
    return last
# endregion


# region: boyer_moore
def boyer_moore(text, pattern):
    """Find every occurrence of `pattern` in `text` using the bad-character rule. Align the
    pattern, compare right-to-left; on a mismatch at text character c, shift the pattern forward
    so c's rightmost occurrence in the pattern lines up under it (never less than 1). Characters
    the shift jumps over are never examined — the source of the sublinear behavior. Returns
    (matches, examined) where `examined` counts text characters actually looked at."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    if m > n:
        return [], 0
    last = last_occurrence(pattern)
    matches, examined = [], 0
    i = 0                                        # index in text where the pattern's left end sits
    while i <= n - m:
        j = m - 1                                # start comparing from the RIGHT end of the pattern
        while j >= 0:
            examined += 1
            if text[i + j] != pattern[j]:
                break
            j -= 1
        if j < 0:                                # ran off the left end → full match
            matches.append(i)
            i += 1                               # shift by one to find overlapping matches
        else:
            c = text[i + j]                      # the mismatching text character
            shift = j - last.get(c, -1)          # align c with its rightmost spot in the pattern
            i += max(1, shift)                   # never stall; skip the chars in between unexamined
    return matches, examined
# endregion

"""The library counterpart and the contrast. Python's `str.find` (C, a two-way hybrid) is the
correctness reference. The instructive contrast is KMP from two chapters ago: KMP examines every
one of the n text characters (it's O(n) and never skips), while Boyer-Moore skips ahead and
examines fewer than n on average. Counting characters examined by each is what reveals
Boyer-Moore's sublinear behavior — and why real tools like grep are built on it.

`kmp_search` below returns matches AND its examined-character count, for the head-to-head.
"""


# region: kmp
def _prefix(pattern):
    m = len(pattern)
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps


def kmp_search(text, pattern):
    """KMP with an examined-character counter. It reads every text character (advancing i through
    all n), so its count is ~n regardless of pattern length — the flat baseline Boyer-Moore beats
    by skipping. Returns (matches, examined)."""
    if not pattern:
        return list(range(len(text) + 1)), 0
    lps = _prefix(pattern)
    matches, examined, j = [], 0, 0
    for i in range(len(text)):
        examined += 1                            # KMP looks at every text character exactly once here
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = lps[j - 1]
    return matches, examined
# endregion


# region: builtin
def find_all_builtin(text, pattern):
    """All occurrences via str.find — the trusted correctness reference."""
    if not pattern:
        return list(range(len(text) + 1))
    out, i = [], text.find(pattern)
    while i != -1:
        out.append(i)
        i = text.find(pattern, i + 1)
    return out
# endregion

Scratch vs library

Boyer-Moore against KMP is a study in two opposite strategies for the same problem, and neither is simply "better." KMP is steady: linear, deterministic, examines every character, never worse than $O(n)$ — the algorithm you want when the worst case matters or the alphabet is tiny. Boyer-Moore is opportunistic: it bets that most alignments can be dismissed with one glance and a big jump, which pays off enormously on large alphabets and long patterns but can degrade on adversarial repetitive input. The face-off's descending line is the signature of that bet paying off. This is the same average-case-versus-worst-case tension seen with quicksort (fast average, quadratic worst) versus merge sort (steady) — and the practical answer is the same: know which regime you're in. Real text over a big alphabet? Boyer-Moore, which is why grep uses it. Untrusted input or a tiny alphabet? A linear guarantee. In production str.find picks a hybrid for you; building Boyer-Moore yourself is what makes "longer pattern, faster search" a fact you've measured rather than a paradox.

Where you'll actually meet it

Boyer-Moore and its variants are the substring search of the real world. GNU grep uses Boyer-Moore- Horspool (and Commentz-Walter, a multi-pattern Boyer-Moore, for multiple fixed strings) — its famous speed comes from skipping input it never reads. Text editors and IDEs use it for find-in-file. Many language standard libraries implement indexOf/find/str.find with Boyer-Moore-family or two-way hybrid algorithms. Antivirus and intrusion-detection scanners use it (and multi-pattern extensions) to hunt signatures. It appears in log analysis, in memmem-style byte-search routines deep in operating systems, and anywhere large volumes of text or binary data must be scanned for fixed patterns. If you've ever been surprised how fast grep chews through a huge file, this skipping is why.

Takeaways

Boyer-Moore searches by comparing the pattern to the text right-to-left and, on a mismatch, shifting the pattern forward to align the offending text character with its rightmost occurrence in the pattern — leaping the whole pattern length when that character is absent. This lets it examine fewer than $n$ characters, running sublinearly on average, with the singular property that a longer pattern searches faster (24× fewer examinations than KMP at pattern length 64). The bad-character rule alone has a quadratic worst case, cured by the good-suffix rule; the simplified Horspool variant is what most real tools, including grep, actually ship.

The single-pattern trilogy — KMP's automaton, Rabin-Karp's fingerprint, Boyer-Moore's skipping — is now complete, three distinct philosophies for finding one pattern. The next two chapters change the question. Suffix arrays (next) preprocess the text itself into a searchable index, so that after an $O(n \log n)$ build, any pattern can be found in $O(m \log n)$ — the right trade when you'll search the same text many times. And Aho-Corasick builds one automaton to match thousands of patterns at once. The field moves from "search a text once" to "index a text, or match many patterns" — the problems that scale.