Boyer-Moore, in depth: bad character and strong good suffix rules, building the tables, a full trace and the Galil worst-case fix

The idea: compare backwards, skip forwards

Call the pattern P with length m, the text T with length n, and an alignment s the position where P[0] sits over T[s]. The naive algorithm tries every s from 0 to n - m and compares up to m characters at each. Boyer-Moore keeps the same outer loop over alignments but changes two things. It compares P[m-1] first and walks left, and when a comparison fails it shifts s by more than one, using information it has just learned.

What it has learned at a mismatch at pattern index j is two facts. First, the text character T[s+j] is some character x that is not P[j]. Second, the suffix P[j+1..m-1] matched the text exactly. Each fact supports a rule that rules out a range of alignments. The bad character rule uses x: slide the pattern right until its rightmost x sits under the text x, or past it if x does not appear. The good suffix rule uses the matched tail t: slide until another copy of t in the pattern, preceded by a different character, sits under the text t, or until a prefix of the pattern lines up with a suffix of t. Both shifts are safe, meaning no alignment they skip can be a match, so the algorithm takes the larger one.

The bad character rule

The bad character table records, for every character, the index of its last occurrence in the pattern, or -1 if it does not occur. At a mismatch at index j against text character x the bad character shift is j - last[x]. If x occurs only to the left of j this lines it up. If x does not occur, the shift is j + 1, moving the whole pattern past the bad character. If the last x is to the right of j, the formula gives a negative number; that is why plain bad-character search needs a floor of 1 and why Boyer-Moore pairs it with a second rule that always gives at least 1.

For EXAMPLE the table is E: 6, X: 1, A: 2, M: 3, P: 4, L: 5, and -1 for everything else. Note that E maps to 6, not 0; only the rightmost occurrence matters for the shift formula.

def bad_char_table(pat):
    """Rightmost index of each character in pat; absent characters default to -1."""
    last = {}
    for i, ch in enumerate(pat):
        last[ch] = i
    return last

For bytes, use a 256-entry integer array so the lookup is one load. For Unicode, search the UTF-8 bytes (a byte match of a valid UTF-8 pattern is a character match) or keep a small hash map.

The strong good suffix rule

Suppose the suffix t = P[j+1..m-1] has matched and P[j] mismatched. The good suffix shift is the smallest shift that is consistent with what the text is known to contain. There are two cases. In case 1, t occurs again somewhere else in the pattern and the character before that occurrence differs from P[j]; we shift so that occurrence sits under the text t. Requiring the preceding character to differ is the strong good suffix rule. Without it the shift can line up the same failing character again, and the worst-case guarantees disappear. In case 2, no such occurrence exists, but some prefix of the pattern equals a suffix of t; we shift so that the longest such prefix sits under the end of the text. If neither applies, shift by m.

The table is built in O(m) using borders (a border is a proper prefix that is also a suffix). The first loop fills case 1 shifts; the second fills the rest from the widest border of the whole pattern.

def good_suffix_table(pat):
    """gs[j+1] is the safe shift after a mismatch at pat[j]; gs[0] is the shift after a full match."""
    m = len(pat)
    shift = [0] * (m + 1)
    border = [0] * (m + 1)
    i, j = m, m + 1
    border[i] = j
    while i > 0:                               # case 1: strong good suffix
        while j <= m and pat[i - 1] != pat[j - 1]:
            if shift[j] == 0:
                shift[j] = j - i
            j = border[j]
        i -= 1
        j -= 1
        border[i] = j
    j = border[0]                              # case 2: a prefix matches part of the suffix
    for i in range(m + 1):
        if shift[i] == 0:
            shift[i] = j
        if i == j:
            j = border[j]
    return shift

For EXAMPLE the table is [6, 6, 6, 6, 6, 6, 6, 1]. The last entry, used when the very first comparison fails, is 1: nothing has matched, so the rule contributes only the minimum. Every other entry is 6 because no matched tail recurs inside the pattern, and the only border of EXAMPLE is E, so the pattern can move until its leading E sits where the trailing E was, a shift of m - 1 = 6. The table is easy to get subtly wrong, so test it against brute force, as the next section does.

The search loop and a brute-force test

The search loop is short once the tables exist. Compare right to left; on a full match record s and shift by gs[0], the pattern's period, so overlapping matches are found; on a mismatch take the larger of the two shifts.

def boyer_moore(text, pat):
    n, m = len(text), len(pat)
    if m == 0:
        return list(range(n + 1))
    last = bad_char_table(pat)
    gs = good_suffix_table(pat)
    hits, s = [], 0
    while s <= n - m:
        j = m - 1
        while j >= 0 and pat[j] == text[s + j]:
            j -= 1
        if j < 0:
            hits.append(s)
            s += gs[0]
        else:
            s += max(j - last.get(text[s + j], -1), gs[j + 1])
    return hits


import random

def brute(text, pat):
    return [i for i in range(len(text) - len(pat) + 1) if text[i:i + len(pat)] == pat]

for _ in range(5000):                        # small alphabets expose border bugs fast
    pat = "".join(random.choice("ab") for _ in range(random.randint(1, 6)))
    txt = "".join(random.choice("ab") for _ in range(random.randint(0, 40)))
    assert boyer_moore(txt, pat) == brute(txt, pat), (txt, pat)

A two-letter alphabet produces dense repetition, exactly where a wrong border index skips a real match. A test on English sentences would pass almost any buggy version.

Worked example: EXAMPLE in a sentence

Search for EXAMPLE (m = 7) in HERE IS A SIMPLE EXAMPLE (n = 24). Running the code above with a trace gives five alignments and 15 character comparisons in total, against 18 alignments for the naive algorithm.

The third alignment shows why the good suffix rule earns its complexity. The bad character rule alone would move 3, just past the I, to an alignment that puts X over the already-matched P and so cannot match. The good suffix rule knows the text ends in MPLE, that MPLE appears nowhere else in the pattern, and that only the leading E could line up, so it moves 6. After the match at 17, gs[0] = 6 moves s to 23, which is past n - m = 17, and the search ends.

Cost: sublinear on average, quadratic without care

Preprocessing costs O(m + σ) time, where σ is the alphabet size if you use an array. The search is where Boyer-Moore is unusual. Its best case is about n / m comparisons, sublinear in the text. On a random 100,000-character text over 26 letters and a space, searching for the 16-character pattern pattern matching with the code above made 8,174 alignments and 8,524 comparisons, under one comparison for every eleven text characters. Longer patterns skip further.

The worst case is the catch. Searching for all occurrences of aaaaaaaaaa in a text of 1,000 a characters makes 991 alignments, each of which compares all ten characters again: 9,910 comparisons, the O(nm) behaviour of the naive algorithm. The algorithm forgets what it verified after every match. The Galil rule fixes it: after a match the pattern moves by its period p, and the first m - p characters of the new alignment are already known to match, so the comparison loop stops at index m - p instead of 0.

def boyer_moore_galil(text, pat):
    n, m = len(text), len(pat)
    last, gs = bad_char_table(pat), good_suffix_table(pat)
    hits, s, lo = [], 0, 0
    while s <= n - m:
        j = m - 1
        while j >= lo and pat[j] == text[s + j]:
            j -= 1
        if j < lo:                             # matched down to the known-good prefix
            hits.append(s)
            s += gs[0]
            lo = m - gs[0]                     # this much is already verified
        else:
            s += max(j - last.get(text[s + j], -1), gs[j + 1])
            lo = 0
    return hits

On the same all-a input this version makes 1,000 comparisons, one per alignment plus the first full check. With the strong good suffix rule and the Galil rule together the search is O(n + m) in the worst case. Richard Cole's 1991 analysis bounds the first-occurrence search with the strong rule at about 3n comparisons, which is the classical guarantee people cite.

Boyer-Moore in production

In a real tool the textbook algorithm is only a starting point.

• Memory and branches beat comparison count. Production code uses a byte-indexed array, and many implementations drop the good suffix rule for Horspool's simplification, whose inner loop is tighter while its shifts on natural text are nearly as long.
• Skip loops. The hot loop is usually an unrolled loop that tests only the last character, or a vectorised scan for a rare pattern byte, with a full comparison only on a candidate. Mike Haertel's well-known note on why GNU grep is fast describes this.
• Multiple patterns change the problem. Boyer-Moore searches for one pattern. For many patterns use Aho-Corasick or a Commentz-Walter style automaton, and for approximate matching see Bitap.

Regex engines use the same idea as a prefilter: extract a required literal and find it with a skip search before running the automaton, as described in Regular Expressions, in depth.

Failure modes

• Weak good suffix rule. Omitting the 'different preceding character' condition still finds every match but can make long sequences of short shifts on periodic text.
• Off-by-one in the gs index. A mismatch at j uses gs[j+1]. Using gs[j] overshoots and misses the match at 17 in the example above.
• Missing overlapping matches. Shifting by m after a match misses aa at position 1 in aaa. Shift by gs[0].
• Character units. Code units, code points and graphemes give different answers; normalise both sides (NFC) and decide on case folding before building the tables.
• Small alphabets. On DNA almost every character occurs near the end of the pattern, so bad character shifts are tiny; bit-parallel methods often win there.
• Adversarial input. A service that accepts both pattern and text from users can be pushed into the quadratic case unless the Galil rule, or an algorithm with a linear bound such as KMP or the Z-algorithm, is used.

Trade-offs

Boyer-Moore pays a table and a trickier implementation for the ability to skip text. That pays off when patterns are long, the alphabet is large and the text is in memory.

What to do next

1. Implement bad_char_table, good_suffix_table and the search loop, then run the randomised brute-force test over a two-letter alphabet until it passes 10,000 cases.
2. Print the good suffix table for ABCXXABC and AAAA and explain each entry by hand.
3. Add the Galil rule and confirm the all-a test drops from 9,910 to 1,000 comparisons.
4. Benchmark against your language's built-in find on real data; expect the built-in to win on short patterns and decide whether you need Boyer-Moore at all.
5. Decide your character unit (bytes, code points or normalised text) and test with accented input.
6. If users supply patterns, cap pattern length and guarantee a linear worst case.