---
title: Boyer–Moore
source: 'https://academia.sh/en/courses/algorithms/boyer-moore'
course: Algorithms
language: en
updated: '2026-08-17T18:07:45+00:00'
license: 'CC BY-SA 4.0'
---

# Boyer–Moore

Matching from the end, the bad-character and good-suffix rules, the Horspool simplification, sublinear behavior, and a measured comparison of four algorithms.

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.

```python
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**.

```python
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.

```python
# 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.

```python
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.

```python
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.