Oh My Algorithm
Algorithm Guidecomplexity: Best O(n / m)

Boyer-Moore

A search that compares the pattern from its right end and, on a mismatch, jumps the pattern far ahead using the bad-character rule. Skipping many text characters makes it one of the fastest single-pattern searches in practice.

01Boyer-Moore

Boyer-Moore starts. It compares the pattern from the right end and, on a mismatch, jumps far ahead using the bad-character rule.

offset 0 · compare the pattern's last char C with text[2]=A — mismatch.

The mismatched text char 'A' sits at pattern index 0. Jump the pattern that far — 2 cells to the right.

offset 2 · compare the last char C with text[4]=A again — another mismatch. Jump by the same rule.

offset 4 · from the right, C=C, B=B, A=A all match.

The pattern matches fully at index 4 — found!

One mismatch skips several cells, never even looking at many text chars — best case O(n/m).

text
A
B
A
A
A
B
C
D
A
B
C
pattern
1 / 7

02 Understand It Simply

For Everyone
🔑How It Works

Matches from the last character of the pattern backwards and, on a mismatch, skips several positions at once based on the offending character. The longer the text and pattern, the better it does.

💡In Plain Words

Compares the pattern from its right end and, depending on the mismatched character, jumps the pattern far ahead.

Skipping many characters makes it among the fastest in practice.

📍Where It's Used
  • –Text-editor find/replace
  • –grep
  • –large-scale search

03 Python Implementation

A clean, readable reference implementation of the core logic of Boyer-Moore.

core_implementation.py
def boyer_moore(text, pattern):
    n, m = len(text), len(pattern)
    last = {ch: i for i, ch in enumerate(pattern)}  # bad-character table
    s = 0
    while s <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
        if j < 0:
            return s                  # match found
        s += max(1, j - last.get(text[s + j], -1))
    return -1

04 Frequently Asked Questions

FAQ
What is Boyer-Moore?+

A search that compares the pattern from its right end and, on a mismatch, jumps the pattern far ahead using the bad-character rule. Skipping many text characters makes it one of the fastest single-pattern searches in practice.

What is the time complexity of Boyer-Moore?+

The time complexity of Boyer-Moore is Best O(n / m). Follow the step-by-step visualization to see exactly why.

Where is Boyer-Moore used?+

Text-editor find/replace, grep, large-scale search.

What's a simple analogy for Boyer-Moore?+

Matches from the last character of the pattern backwards and, on a mismatch, skips several positions at once based on the offending character. The longer the text and pattern, the better it does.

→ Strings — see allRelated
🔤KMP (Knuth-Morris-Pratt)
O(n + m)
🔤Rabin-Karp
Avg O(n + m)