Boyer–Moore

KMP looked at every text character at least once; this looks like a lower bound on linear cost. The Boyer–Moore family breaks this intuition: it is possible to produce the correct result without ever looking at some characters.

The idea comes from a change of direction — the pattern is matched from the end toward the start.

Why Matching from the End Pays Off

The pattern is placed over a window of the text, and comparison starts from the last character. If the mismatch occurs at the very end, the text character at that point determines how far the pattern can be shifted.

If the text character does not occur at all in the pattern, the pattern can be shifted entirely past it: a single comparison eliminates $m$ positions. The characters in between are never looked at.

If it does occur in the pattern, the pattern is shifted just far enough to align its rightmost occurrence of that character with the text. This is the bad-character rule.

The Shift Table

The rule is applied with a simple table derived from the pattern: for each character, its distance from the end of the pattern.

def shift_table(pattern: str) -> dict[str, int]:
    """A character's distance from the end of the pattern; the last character is excluded."""
    m = len(pattern)
    return {pattern[i]: m - 1 - i for i in range(m - 1)}


print(shift_table("ABABCABAB"))     # {'A': 1, 'B': 2, 'C': 4}

The table is built from m - 1 characters; the last character is left out, because the shift must always be at least one. For a character not in the table, the shift is $m$.

Values are computed from the rightmost occurrence in the pattern: if the same character occurs more than once, the last assignment in the dictionary remains, and that corresponds to the rightmost position.

The Horspool Variant

The short, widely used simplification of Boyer–Moore bases the shift not on the mismatching character but on the last character of the window.

def horspool(text: str, pattern: str) -> tuple[list[int], int]:
    """(positions, character-comparison count)"""
    n, m = len(text), len(pattern)
    if m > n:
        return [], 0
    table = shift_table(pattern)
    positions: list[int] = []
    shift, count = 0, 0

    while shift <= n - m:
        j = m - 1
        while j >= 0:                       # compare from end to start
            count += 1
            if text[shift + j] != pattern[j]:
                break
            j -= 1
        if j < 0:
            positions.append(shift)
            shift += 1
        else:
            last = text[shift + m - 1]
            shift += table.get(last, m)     # not in table: skip a full pattern length
    return positions, count


text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(horspool(text, pattern))       # ([10], 20)
print(horspool("ABABAB", "AB"))      # ([0, 2, 4], 8)
print(horspool("aaa", "b"))          # ([], 3)

Because the shift is always at least 1, termination is guaranteed. Correctness rests on the rule guaranteeing that the skipped positions cannot contain a match: the shift goes only as far as the nearest alignment at which the window’s last character could occur in the pattern.

The Measured Difference

Comparing all four algorithms on the same inputs makes the difference in direction visible in numbers.

# brute_force and kmp: the implementations from the previous two lessons, brought
# in here so the block can run on its own
def brute_force(text: str, pattern: str) -> tuple[list[int], int]:
    """(positions found, character-comparison count)"""
    n, m = len(text), len(pattern)
    positions: list[int] = []
    count = 0
    for shift in range(n - m + 1):
        j = 0
        while j < m:
            count += 1
            if text[shift + j] != pattern[j]:
                break
            j += 1
        if j == m:
            positions.append(shift)
    return positions, count


def prefix_function(pattern: str) -> list[int]:
    """pi[i]: the longest proper prefix-suffix length of pattern[0..i]."""
    pi = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k > 0 and pattern[i] != pattern[k]:
            k = pi[k - 1]                  # fall back to a shorter candidate prefix
        if pattern[i] == pattern[k]:
            k += 1
        pi[i] = k
    return pi


def kmp(text: str, pattern: str) -> tuple[list[int], int]:
    """(positions, character-comparison count)"""
    pi = prefix_function(pattern)
    positions: list[int] = []
    k = 0
    count = 0
    for i, character in enumerate(text):
        while k > 0 and character != pattern[k]:
            count += 1
            k = pi[k - 1]
        count += 1
        if character == pattern[k]:
            k += 1
        if k == len(pattern):
            positions.append(i - len(pattern) + 1)
            k = pi[k - 1]                  # do not miss an overlapping next occurrence
    return positions, count


long_text = ("the cost of searching for a pattern inside a text depends on "
             "how large the alphabet is and on repetition. ") * 10

for query in ("pattern", "repetition", "zzzzz"):
    print(query,
          brute_force(long_text, query)[1],
          kmp(long_text, query)[1],
          horspool(long_text, query)[1])

# pattern    1144 1090 250
# repetition 1181 1100 260
# zzzzz      1056 1060 212
#                        ← text length: 1060

Horspool makes fewer comparisons than the text’s length: 250 to 260 on a 1060-character text, well under the total. As the pattern grows longer, the count drops further, because a larger step is taken on every failed attempt.

This sublinear behavior is not a contradiction: the algorithm does not look at every character of the text. Showing that the pattern is absent does not require reading the entire text.

The expected comparison count approaches $n/m$ as the alphabet size $\sigma$ grows. Because natural language and large alphabets satisfy this condition, matching from the end is the typical choice of text-search tools.

Worst Case and the Good-Suffix Rule

With the bad-character rule alone, the worst case stays $O(nm)$. On small-alphabet, repetitive inputs, the shifts shrink.

print(horspool("A" * 30 + "B", "A" * 10 + "B")[1])     # 31
print(brute_force("A" * 30 + "B", "A" * 10 + "B")[1])  # 231

On this input the result is good, because the mismatch shows up on the first comparison. The reverse construction — a pattern such as "BAAAAAAAAA" inside "A"*30 — brings the shifts down to one.

Full Boyer–Moore adds the good-suffix rule to the bad-character rule: if the matched suffix occurs elsewhere in the pattern, the pattern is aligned to that occurrence; if it does not, a prefix of the suffix is aligned to the start of the pattern. Whichever rule proposes the larger shift is chosen.

The good-suffix table is built in $O(m)$, in a manner similar to KMP’s prefix function. With an additional technique (a rule that prevents already-matched regions from being recompared), the worst case can be brought down to $O(n)$.

Looking One Past the Window

Another variant in the same family bases the shift not on the window’s last character but on the character immediately after the window. Because that character will remain inside the pattern at the next alignment, $m+1$ positions can be skipped at once if it does not occur in the pattern at all.

def quick_search(text: str, pattern: str) -> tuple[list[int], int]:
    n, m = len(text), len(pattern)
    if m > n:
        return [], 0
    table = {pattern[i]: m - i for i in range(m)}     # every character is in the table
    positions: list[int] = []
    shift, count = 0, 0

    while shift <= n - m:
        j = 0
        while j < m:
            count += 1
            if text[shift + j] != pattern[j]:
                break
            j += 1
        if j == m:
            positions.append(shift)
        if shift + m >= n:
            break
        shift += table.get(text[shift + m], m + 1)
    return positions, count


print(quick_search(text, pattern))            # ([10], 14)
print(quick_search(long_text, "repetition")[1])    # 228

Here the comparison direction is start to end; the gain comes entirely from the shift rule. The table covering every pattern character, and the shift being able to reach $m+1$, shortens the implementation while producing large steps in practice.

Where the Four Methods Stand

Criterion	Brute force	Rabin–Karp	KMP	Boyer–Moore
Preprocessing	None	$O(m)$	$O(m)$	$O(m + \sigma)$
Expected	$O(n)$ (large alphabet)	$O(n + m)$	$O(n + m)$	close to $O(n/m)$
Worst case	$O(nm)$	$O(nm)$	$O(n + m)$	$O(n)$ (full form)
Extra space	$O(1)$	$O(1)$	$O(m)$	$O(m + \sigma)$
Stream data	Suitable	Suitable	Suitable	Not suitable

The last row is the cost of matching from the end: because the algorithm moves backward within the window, a single forward pass over the text is not enough.

The choice criterion is this: if the alphabet is large and the pattern is long, Boyer–Moore; if a worst-case guarantee or stream processing is needed, KMP; if many patterns are searched for at once, Rabin–Karp; for short text and a one-time search, brute force.

Summary

• The Boyer–Moore family matches the pattern from end to start; this makes it possible to skip some text characters without ever looking at them.
• The bad-character rule aligns to the rightmost occurrence of the mismatching text character in the pattern; if it does not occur, a full pattern length is skipped.
• The Horspool variant bases the shift on the window’s last character and works with a single table.
• The expected comparison count approaches $n/m$ as the alphabet grows; measured, it drops below the length of the text.
• Adding the good-suffix rule brings the worst case down to linear.
• Matching from the end does not suit stream data; it moves backward within the window.

Next Step

All four algorithms preprocessed the pattern; the text was scanned from scratch on every search. If thousands of queries will be made against the same text, the balance reverses: it becomes cheaper to preprocess the text once and answer every query at logarithmic cost. The next lesson takes up the structures that organize all of a text’s suffixes — the suffix array and the suffix tree.