Boyer-Moore String Matching, in depth: Horspool and Sunday variants, expected cost, alphabet design and how libraries ship it

The idea in one paragraph

Align the pattern of length m against a window of the text and compare from the right end of the pattern. When a comparison fails, the text character you just read tells you something: if it does not occur in the pattern at all, no alignment that covers it can match, so the pattern can jump completely past it. Reading from the right means the first character examined is the one that can justify the longest jump.

Full Boyer-Moore combines two shift rules and takes the larger: the bad character rule, which realigns the mismatched text character with its last occurrence in the pattern, and the good suffix rule, which realigns the already matched suffix with another occurrence of it. The good suffix table is subtle to build and is where most hand-written implementations have bugs. That cost is why the variants below drop it.

Horspool: one table, one lookup

Horspool (1980) keeps only a bad character table, and always looks up the text character aligned with the last pattern position, whether or not that is where the mismatch happened. The shift for character ch is the distance from its last occurrence in the first m - 1 pattern positions to the end of the pattern, or m if it does not occur there. Excluding the last position is essential: including it gives a shift of 0 for the pattern's final character and an infinite loop.

def horspool_table(pat):
    m = len(pat)
    shift = {}
    for i, ch in enumerate(pat[:-1]):   # the last character is excluded on purpose
        shift[ch] = m - 1 - i
    return shift

def horspool(text, pat):
    m, n = len(pat), len(text)
    if m == 0:
        return 0
    shift = horspool_table(pat)
    pos = 0
    while pos <= n - m:
        j = m - 1
        while j >= 0 and text[pos + j] == pat[j]:
            j -= 1
        if j < 0:
            return pos
        pos += shift.get(text[pos + m - 1], m)
    return -1

The worked example in the figure searches for EXAMPLE in the sentence HERE IS A SIMPLE EXAMPLE. The table gives E 6, X 5, A 4, M 3, P 2, L 1, everything else 7. Horspool checks five windows and makes 15 character comparisons before reporting index 17; a naive left-to-right scan of the same text makes 27. The gap grows with pattern length.

Sunday Quick Search and the rest of the family

Sunday's Quick Search (1990) makes one change: after a failed window it looks at the text character just past the window. That character must be part of the next alignment, so the shift can be m + 1 when it does not occur in the pattern, and the table now includes the last pattern position. The comparison order inside the window no longer matters, so implementations use whatever is fastest, often a memcmp.

def sunday(text, pat):
    m, n = len(pat), len(text)
    if m == 0:
        return 0
    shift = {ch: m - i for i, ch in enumerate(pat)}  # later occurrences overwrite earlier ones
    pos = 0
    while pos <= n - m:
        if text[pos:pos + m] == pat:
            return pos
        if pos + m >= n:
            return -1
        pos += shift.get(text[pos + m], m + 1)
    return -1

Other members of the family trade preprocessing for skip length. Raita compares the last, first and middle characters before the rest, which helps on text with long common prefixes. Turbo-BM and Apostolico-Giancarlo remember what previous windows matched to bound total work. In practice, the Horspool and Sunday loops plus good engineering cover most needs.

Expected cost and the alphabet

On random text over an alphabet of size sigma, a window usually fails on the first or second comparison, so cost is dominated by the number of windows, which is n divided by the average shift. When sigma is large compared with m, most text characters are absent from the pattern, shifts are close to m, and the cost approaches n/m comparisons: sublinear, and better the longer the pattern.

When the alphabet is small this breaks down. The shift is the distance to the last occurrence of the window's final character in the pattern, and with sigma = 4 almost every character occurs within the last few positions of any reasonable pattern. The average shift is then about sigma, not m, however long the pattern is. One run on 100,000 random characters with a 16-character pattern illustrates it:

The standard fix for small alphabets is to index the shift table by pairs or longer q-grams of characters, which raises the effective alphabet to sigma squared. glibc's strstr does exactly this: since 2019 it uses a modified Horspool algorithm whose bad character table is indexed by a hash of character pairs, for needles up to 256 bytes, so shifts fit in one byte and the table stays cache friendly. Longer needles use a filtering step and, for very long ones, the Two-Way algorithm.

Worst cases and untrusted input

Horspool and Sunday are O(nm) in the worst case. Search for b followed by nine a characters in a text of 1,000 a characters: every window matches nine characters from the right, fails on the b, and shifts by one. That is 9,910 comparisons, ten times the 991 a naive left-to-right scan needs on the same input, because naive search fails on its first comparison.

This matters whenever an attacker chooses the pattern or the text: a search box over logs, a filter rule in a proxy, a user-supplied find in an editor plugin. Inputs like this are a cheap denial of service. The options are full Boyer-Moore with the Galil rule, which is linear, or an algorithm with a linear worst case by design, such as KMP, the Z-algorithm or Two-Way. CPython took the second route: since 3.10 its forward searches (find, index, replace and friends) use an enhanced Two-Way algorithm for sufficiently long needles, removing a quadratic worst case; reverse searches such as rfind were not changed.

Designing the shift table

• Bytes. A 256-entry array indexed by byte is the fastest table. Fill it with m (or m + 1 for Sunday) and overwrite the pattern's characters; preprocessing is O(m + 256).
• UTF-8 text. Search the bytes, not decoded code points. UTF-8 is self-synchronising: a valid UTF-8 pattern can only match a valid UTF-8 text at a character boundary, so byte search returns correct character matches and keeps the small table.
• Code points or wide characters. A dense table over 1.1 million code points is wasteful. Use a dictionary, or a 256-entry table indexed by the low byte, which only shortens some shifts and stays correct, because a shorter shift never skips a match.
• Case-insensitive search. Fold the pattern and text the same way first. Full Unicode case folding can change lengths (German sharp s folds to ss), so indices in the folded text must be mapped back to the original.
• Small table entries. Capping shifts at 255 lets entries be one byte, which keeps the table in L1 cache. A capped shift is still safe for the same reason as above.

Testing a shift table

Shift tables are easy to get almost right. The cheapest protection is differential testing against a trusted implementation on small random alphabets, where repeats and overlaps are frequent. Both functions above pass this test against Python's str.find over 200,000 random cases, including empty patterns and patterns longer than the text:

import random

def test_against_find(search, trials=200_000):
    for _ in range(trials):
        sigma = random.choice(["ab", "abc", "acgt", "abcdefghij"])
        text = "".join(random.choice(sigma) for _ in range(random.randint(0, 40)))
        pat = "".join(random.choice(sigma) for _ in range(random.randint(0, 6)))
        assert search(text, pat) == text.find(pat), (text, pat)

test_against_find(horspool)
test_against_find(sunday)

Add three targeted cases a random test rarely hits: a pattern whose last character also occurs earlier in it, a match at the very end of the text, and the all-a worst case with a time limit, so a regression to quadratic behaviour fails loudly.

How production libraries do it

Fast library searches are rarely a textbook loop. Common techniques:

• Skip loop first. Run a tight loop that only reads the character under the window's end and shifts, and enter the verification loop only when that character equals the pattern's last character. This was the core of Hume and Sunday's tuned Boyer-Moore.
• Vectorised candidate scan. Use SIMD to find positions where one or two chosen pattern bytes occur, then verify each candidate. Picking bytes that are rare in typical text makes candidates rare. For short needles this often beats any skip table.
• Algorithm switching. Libraries choose by needle length: a direct loop for 1 to 3 characters, a Horspool-like search in the middle, a linear-time algorithm for long needles. They also switch when a search is doing too much work for its progress.
• Preprocess once. Table construction is O(m + sigma). For a pattern searched across many documents, build it once and reuse it; for one search in a 100-byte string, a plain loop wins.

Many patterns at once are a different problem: run Aho-Corasick rather than one Boyer-Moore pass per pattern.

Failure modes

• Including the last character in the Horspool table. The final character gets shift 0 and the loop never terminates.
• Shifting by m after a match when overlaps matter. Searching aa in aaa should find positions 0 and 1 if overlaps are wanted; shift by the period or by 1 after a match.
• Reading past the text. Sunday's lookahead reads text[pos + m], which does not exist for the last window; check the bound first, as the code above does.
• Signed char indexing. In C, indexing a 256-entry table with a plain char gives negative indices for bytes above 127; cast to unsigned char.
• Trusting average-case numbers. Benchmarks on English prose hide the small alphabet slowdown and the adversarial worst case. Benchmark on your real data and on hostile inputs.

Trade-offs

What to do next

1. Implement Horspool and Sunday from this article and run the differential test against your language's built-in search.
2. Trace one search by hand with a pattern that repeats its last character, and check each shift against the table.
3. Measure windows and comparisons on your real data, and compare with a small-alphabet sample.
4. Time the b-then-a worst case; if users can supply patterns or text, pick a linear-time algorithm.
5. Read your standard library's search source to see which algorithm it actually uses before replacing it.
6. Work through the good suffix table in the companion article and add it, with the Galil rule, if you need a linear-time Boyer-Moore.