Right-to-Left Scanning and the Boyer-Moore Shift Tables

Every matcher discussed so far reads the text left to right and the pattern left to right. Boyer and Moore reversed the second of those. The pattern is compared against a window starting at its last character and moving backwards, and a mismatch at the right end is far more informative than one at the left end, because the character that caused it appears in the text at a known offset from the window start. If that character does not occur in the pattern at all, no alignment overlapping it can match, and the window can jump past it entirely.

The consequence is that the algorithm reads fewer than n characters on typical input. On natural-language text with a pattern of moderate length, most alignments are rejected after one or two comparisons, and each rejection shifts the window by several characters. The asymptotic worst case is not better than the left-to-right methods, but the constant is.

The mismatch that carries information

Take a pattern of length m aligned so that its last character sits at text position i. Comparison proceeds from pattern position m−1 down to 0. Suppose the first mismatch is at pattern position j, with text character c = T[i − (m−1) + j].

Two facts are now established. First, the substring of the text aligned with pattern positions j+1 to m−1 equals that suffix of the pattern. Second, the text at the mismatch position is c, and c differs from P[j].

The bad-character rule uses only the second fact. Let last(c) be the index of the rightmost occurrence of c in the pattern, or −1 if absent. If c occurs in the pattern to the left of j, aligning that occurrence with the text position requires a shift of j − last(c). If c does not occur in the pattern at all, the window moves so that its first character passes the mismatch position, a shift of j + 1. If the rightmost occurrence of c lies to the right of j, no forward shift of at most j can place an occurrence of c under the mismatch, so the rule contributes a shift of one.

The good-suffix rule uses the first fact. The matched suffix of length m−1−j must align with an occurrence of itself elsewhere in the pattern, either as a proper suffix shifted right or as an internal occurrence preceded by a character different from P[j]. The smallest shift satisfying that condition is the good-suffix shift for j. The comparison is against P[j], the pattern character that just failed, rather than against the text character c: a re-occurrence preceded by P[j] would put the same character against c again and fail identically.

Both rules produce a shift distance, and the algorithm takes the larger. Taking the maximum is what makes the method safe: each rule independently guarantees that no alignment skipped by its own shift can match, and a shift at least as large as either therefore also skips only impossible alignments.

Building the two tables

The bad-character table is an array indexed by character, of size |Σ|, holding the rightmost position of each character in the pattern. Construction is one pass, and the memory is 256 entries for a byte alphabet or 4·|Σ| bytes for a 32-bit code point alphabet. For a large alphabet and a short pattern this dominates the pattern itself, which is why some implementations use a hash map or restrict the table to characters that actually appear.

The good-suffix table is the interesting one. Its entry for a mismatch at position j is the smallest shift s such that either s ≤ j, the matched suffix P[j+1..m−1] reappears in the pattern shifted left by s, and the character immediately to the left of that reappearance differs from P[j]; or, when no such internal occurrence exists, the longest suffix of the matched suffix that is also a prefix of the pattern is aligned with that prefix. The first case preserves an internal occurrence; the second slides the whole pattern forward until only a border of the matched suffix still overlaps. The standard construction runs in two passes over the pattern and reuses the border machinery from the prefix function: a backward scan records, for every suffix, the longest prefix of the pattern that is also that suffix; a forward scan then fills the entries for which no internal occurrence exists, using the shift implied by the longest border. Each entry is the distance between the pattern’s end and the start of the realigned occurrence.

The result is an m-entry shift array plus the character table. Preprocessing is O(m + |Σ|) time and space, and it is paid once per pattern. For a single search of a long text this is negligible; for a pattern used once against a short text, it is not, which is why library implementations switch to a simpler scan below a length threshold.

A worked shift sequence

Pattern GCAGAGAG against the text GCAGCGAGTTTGCAGAGAGCCC. The first alignment places the pattern at offset 0 and compares from the right. The last three characters agree, so the matched suffix is GAG, length 3, and the mismatch comes at pattern position 4: pattern A against text C.

The bad-character rule asks where C occurs last in the pattern: index 1. Aligning that occurrence with the text position requires a shift of 4 − 1 = 3. The good-suffix rule looks for another occurrence of GAG preceded by a character other than P[4], which is A. GAG occurs again at index 3, preceded by A, so that occurrence is rejected; no other internal occurrence exists, and the rule falls back to its second case, sliding the pattern forward until the longest border of the matched suffix that is also a prefix of the pattern reaches the front. That border is G, of length 1, so the shift is 8 − 1 = 7. The maximum of the two rules is 7, and the window jumps to offset 7.

At offset 7 the window is GTTTGCAG. The last two characters agree, so the matched suffix is AG, and the comparison fails at pattern position 5: pattern G against text C. The bad-character rule finds C at index 1, a shift of 5 − 1 = 4. The good-suffix rule finds AG again at index 2, preceded by C, which differs from P[5] = G, giving a shift of 6 − 2 = 4. Both rules agree, and the window moves to offset 11, where the whole pattern matches.

The sequence of alignments is offset 0, 7, 11: two mismatches and a match. At offset 0 the good-suffix rule binds and the character table alone would have shifted too little; at offset 7 the two rules agree. On text where the offending character is absent, the bad-character rule usually dominates on its own.

def bad_character_table(p):
    last = {}
    for i, ch in enumerate(p):
        last[ch] = i
    return last

def boyer_moore(text, p):
    m, n = len(p), len(text)
    last = bad_character_table(p)
    good = good_suffix_table(p)      # shift for a mismatch at pattern position j; built as above
    period = m - longest_border(p)   # shift after a full match
    i = m - 1                        # index of the window's last character in text
    while i < n:
        j = m - 1
        while j >= 0 and p[j] == text[i - m + 1 + j]:
            j -= 1
        start = i - m + 1
        if j < 0:
            yield start
            i += period
        else:
            c = text[start + j]
            bad = j - last.get(c, -1)   # shift so the occurrence aligns under j
            i += max(1, bad, good[j])

Two details in that loop are easy to get wrong. The shift after a full match is the pattern’s period, m minus the longest border length, which is the smallest alignment that could still match; a shift of m is always safe but misses overlapping occurrences, which is why the border is consulted. And last.get returning −1 makes bad equal to j + 1, which moves the window’s first character past the mismatch position; the max(1, …) guard matters for the one case where the rightmost occurrence of c sits exactly at j, which would otherwise propose a shift of zero and spin forever.

Why the worst case is still quadratic

The bad-character rule can shift by one at every alignment. Construct a text of repeated a and a pattern that ends in a long run of a preceded by something else: each alignment matches the run and fails at the same relative position, and the shift is small because a occurs immediately to the left of the mismatch. Comparison count then grows with the product of text and pattern length.

The good-suffix rule does not remove the quadratic bound on its own. When the matched suffix is highly periodic, the good-suffix shift is the period of that suffix rather than one character, which avoids the worst shifts the bad-character rule alone would take. The total shift distance over a scan is always linear in the text length, because the window only moves forward; the comparison count is a separate quantity. The pattern’s periodicity determines how many characters are re-examined per shift, and there are inputs on which the two heuristics together still compare Θ(nm) characters. What can be stated plainly is that the two rules together remove the pathological shift behaviour that the bad-character rule permits alone, but not the worst-case comparison count.

A further refinement, due to Galil, applies when the pattern has a short period: after a match, the characters already known to match can be skipped rather than re-compared. With it the comparison count is bounded linearly in the text length, which is why implementations that need a worst-case guarantee add the rule.

Horspool’s simplification and the cost of dropping a rule

Boyer–Moore–Horspool keeps only a variant of the bad-character rule, computed over the m−1 characters of the pattern excluding the last, and always shifts by at least one. The good-suffix table disappears entirely, so preprocessing is one pass over the pattern and the code fits in a few lines. The simplification is not free: the worst case is Θ(nm) on periodic inputs, because nothing prevents the one-character shifts. In exchange the inner loop is small, the table is |Σ| entries rather than m + |Σ|, and for short patterns the smaller constant usually wins. The simplification is attractive when the pattern is a literal supplied at run time, because the preprocessing it avoids dominates when the text is short.

Sunday’s variant shifts using the character immediately after the window rather than the one that caused the mismatch, which tends to produce longer skips on natural language and requires the same single table.

Reading the text backwards is the real constraint

The algorithm’s advantage comes from reading the text in an order that a stream cannot always provide. If the text arrives through a pipe and is not retained, a window of m characters must be buffered, and the buffer must slide; the skip may discard characters that were already read but never examined, which is fine, and may require reading ahead, which costs memory but not correctness. Sliding-window implementations keep exactly m bytes and refill from the stream, and the shift is applied by moving the buffer offset rather than by indexing into a stored text.

The second constraint is the alphabet. The bad-character table is indexed by character, so a matcher over UTF-8 bytes treats each byte as a symbol and can produce a shift that lands mid-sequence. For searching user-visible text this is wrong in the same way it is wrong for the prefix function matcher: byte offsets are not character offsets, and a match that starts inside a multi-byte sequence is not a match of the text’s characters. Decoding to code points first removes the ambiguity and makes the character table sparse.

Multi-pattern matching does not compose with these tables. Each pattern would need its own pair of tables and its own scan, giving work proportional to the number of patterns. The alternative is to merge all patterns into one automaton, which is what Aho–Corasick does, at the cost of losing the right-to-left skip entirely. Hashing offers a third position: a rolling hash compares windows without reading characters backwards, but its worst case is also quadratic on repetitive input.