Boyer-Moore String Search

A pattern-matching algorithm that scans right to left and skips large sections of text using two shift heuristics.

Matching from the right

The Boyer-Moore algorithm compares a pattern to the text from right to left, and on a mismatch it shifts the pattern forward by as much as possible. Because it can skip many characters at once, it is sublinear on typical text and is the practical basis of many grep and editor search implementations.

Two heuristics

Kronos motion — classical

Bad-character rule: on a mismatch, align the pattern so the mismatched text character lines up with its last occurrence in the pattern (or shift past it entirely if absent).
Good-suffix rule: when a suffix of the pattern has matched, shift so that another occurrence of that suffix, or a matching prefix, aligns with the text.
Each step takes the larger of the two suggested shifts.

Performance

With both rules, Boyer-Moore runs in O(n/m) best case (long patterns over natural-language text) and O(n + m) worst case with the Galil rule. On large alphabets the bad-character rule alone gives big skips; on small alphabets the good-suffix rule matters more. Preprocessing the pattern is O(m + alphabet).

Bad-character table

python

def bad_char_table(pat):
    last = {}
    for i, ch in enumerate(pat):
        last[ch] = i      # rightmost index of each character
    return last

# on mismatch of text char c at pattern index j:
#   shift = max(1, j - last.get(c, -1))

Variants

Boyer-Moore-Horspool simplifies to just the bad-character rule keyed on the last window character, trading worst-case guarantees for simpler, fast code. Sunday's algorithm shifts based on the character just past the window. For multiple patterns, Aho-Corasick is preferred; for guaranteed linear single-pattern search, KMP or the Z-algorithm.