Boyer–Moore

Cost and properties

typical	~n/m compares — sublinear
worst case	~m·n (mismatched-character rule alone)
preprocess	O(R + m)
in practice	the fastest for long patterns

Reference: Sedgewick & Wayne, §5.3; Boyer–Moore 1977.

Boyer–Moore in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def search(pat, txt):
    # Scan the pattern RIGHT to LEFT. On a mismatch, slide the pattern so
    # the offending TEXT character lines up with its rightmost occurrence
    # in the pattern -- if it does not occur at all, skip m characters.
    m, n = len(pat), len(txt)
    right = {}
    for j in range(m):
        right[pat[j]] = j                 # rightmost index of each char
    i = 0
    while i <= n - m:
        skip = 0
        for j in range(m - 1, -1, -1):    # right to left
            if pat[j] != txt[i + j]:
                skip = max(1, j - right.get(txt[i + j], -1))
                break
        if skip == 0:
            return i                      # nothing mismatched: a match
        i += skip
    return n

Why it works

Why backwards

Comparing right to left means a mismatch is usually discovered immediately, and it happens at the far end of the alignment — which tells you a lot. If the offending text character does not appear in the pattern at all, no alignment overlapping it can match, so you may slide the pattern past it entirely: m characters skipped for one compare. That is how the algorithm reads less than the whole text.

The mismatched-character rule

right[c] is the rightmost index of c in the pattern, or −1 if absent. On a mismatch at pattern index j against text character c, the shift is j - right[c], which lines up that occurrence. The max(1, …) matters: when the rightmost occurrence is to the right of j, the formula goes negative and would move the pattern backwards — so the algorithm falls back to a shift of one.

The worst case, and the full algorithm

With only this rule, a pattern like baaaa against a run of a's is still ~m·n — try the worst case preset. The complete Boyer–Moore adds a second rule (the strong good-suffix rule, using a KMP-like preprocessing) which brings the worst case down to linear. Most implementations, including the one here and many library versions, ship only the first rule because it is short and almost always enough.

In practice

Boyer–Moore and its simplified cousin Boyer–Moore–Horspool are what real tools use: GNU grep, many text editors' find, and most language runtimes' indexOf for long needles. The longer the pattern and the larger the alphabet, the bigger the skips — the opposite of the usual intuition that longer patterns cost more.

What to try in the animation

Notice how many text characters are never looked at — that is what “sublinear” means. Fewer repeated characters in the pattern means bigger skips.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• needle in a haystack — text: findinahaystackneedleinahaystack · pattern: needle
• repeated characters — text: abacadabrabracabracadabrabrabracad · pattern: abracadabra
• big skips — text: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaz · pattern: xyz
• worst case — text: aaaaaaaaaaaaaaaaaaaa · pattern: baaaa

Open Boyer–Moore in the player →

The rest of Substring search

• Brute-force substring search Try every alignment, comparing left to right.
• Knuth–Morris–Pratt Precompute, for every state and character, where a mismatch leaves you.
• Rabin–Karp Hash the pattern once, then hash every window of the text — each in constant time from…