Boyer-Moore string matching: a practical tutorial

String matching sits behind search boxes, log filters, route validators and command-line tools. When a program must locate one string inside another, the algorithm choice affects both clarity and throughput. Boyer-Moore is especially instructive because it tries to move past text that cannot possibly match.

A naïve scanner checks each starting position and usually compares from the left. That is easy to explain, yet repetitive data can make it expensive. Boyer-Moore instead compares from the right edge of the pattern, giving mismatches information about how far the whole pattern can slide.

The method was developed by Richard Boyer and J Strother Moore. It preprocesses the pattern, not the full document, and combines two independent skipping ideas: the bad-character rule and the good-suffix rule. The result is a search that often examines only a small part of a large body of text.

Readable Python keeps each decision close to the text. The examples use short words and place names so each shift can be inspected by hand, while the discussion covers complexity, boundary cases and practical choices.

How Boyer-Moore matching works

Imagine a text window the same length as the pattern. The algorithm compares the window’s final character with the pattern’s final character, then works backwards until it finds a mismatch or confirms a full match. A mismatch ends that alignment, but it does not force the next attempt to begin one character later.

Instead, preprocessing determines safe distances. The rightmost mismatching character suggests one distance, while the portion of the pattern that already matched suggests another. Taking the larger safe distance lets the search skip positions without examining their characters individually.

The scan returns the leftmost occurrence because offsets increase from left to right. It does not need every character in the skipped region to be identical to the pattern; it only needs to know that no valid match can begin at the positions being discarded. That distinction is the heart of the method.

The two ways to skip ahead

The bad-character rule focuses on the text character that caused the mismatch. Let j be its index in the pattern and b the last index where that same character occurs in the pattern. The pattern can move by max(1, j - b). If the character never appears in the pattern, the distance becomes j + 1. Aligning the earlier occurrence with the text character, or moving beyond the unmatched region, avoids pointless alignments.

The good-suffix rule uses what remained matched to the right of the mismatch. That suffix may match a prefix of the pattern, so the next alignment can place those equal pieces together. It may also occur elsewhere inside the pattern, allowing the suffix to overlap another copy. A precomputed table records the smallest valid movement for each mismatch position.

Both distances are conservative bounds: a possible match cannot begin before either bound is respected. The search therefore advances by the larger distance. Using the bad-character rule alone gives a simpler variant, while using both rules gives the canonical form and stronger skipping on many patterns.

Pseudocode and a worked example

The pseudocode makes the control flow explicit. A missing table entry is treated as -1, which makes the bad-character distance fall back to j + 1.

function find(text, pattern):
    n = length(text)
    m = length(pattern)

    if m == 0:
        return 0
    if m > n:
        return -1

    last = lastOccurrenceMap(pattern)
    good = buildGoodSuffixShifts(pattern)
    offset = 0

    while offset + m <= n:
        j = m - 1
        while j >= 0 and text[offset + j] == pattern[j]:
            j = j - 1

        if j < 0:
            return offset

        c = text[offset + j]
        bad = max(1, j - last[c])
        offset = offset + max(bad, good[j])

    return -1

For a hand-checked example, search for MELB in XMELBOURNE. At offset zero, the final B is compared with L, so the mismatch occurs at j = 3. L last appeared at index 2 in MELB, giving a bad-character shift of max(1, 3 - 2) = 1. The pattern slides one place and matches at offset 1.

Real strings often need several rounds of alignment rather than one tidy mismatch. Reading each shift against the text makes the algorithm much easier to debug than stepping through framework abstractions. The Kruskal algorithm tutorial offers a similar graph-based exercise in proving that a greedy choice cannot skip a valid solution.

A Python implementation

The Python version below includes both rules. Its good-suffix helper searches possible overlap distances directly, which makes the compatibility condition visible but is not the fastest preprocessing method. The search function follows the same structure as the pseudocode and returns the first leftmost match.

def _good_suffix_shifts(pattern):
    m = len(pattern)
    shifts = [m] * m

    for j in range(m):
        for distance in range(1, m + 1):
            if distance <= j + 1:
                compatible = (
                    pattern[j + 1 - distance:m - distance]
                    == pattern[j + 1:]
                )
            else:
                compatible = (
                    pattern[distance:]
                    == pattern[:m - distance]
                )

            if compatible:
                shifts[j] = distance
                break

    return shifts


def boyer_moore(text: str, pattern: str) -> int:
    n, m = len(text), len(pattern)

    if m == 0:
        return 0
    if m > n:
        return -1

    last_occurrence = {}
    for index, character in enumerate(pattern):
        last_occurrence[character] = index

    good_suffix = _good_suffix_shifts(pattern)
    offset = 0

    while offset + m <= n:
        j = m - 1
        while j >= 0 and text[offset + j] == pattern[j]:
            j -= 1

        if j < 0:
            return offset

        mismatching_character = text[offset + j]
        bad_shift = max(
            1,
            j - last_occurrence.get(mismatching_character, -1),
        )
        offset += max(bad_shift, good_suffix[j])

    return -1


assert boyer_moore("XMELBOURNE", "MELB") == 1
assert boyer_moore("ANABANA", "ANA") == 0
assert boyer_moore("banana", "xyz") == -1
assert boyer_moore("same", "") == 0

The dictionary stores Unicode characters rather than assuming a fixed byte range, so accented letters work without a 256-entry table. The inner loop moves right to left, and the outer loop moves the alignment right. If the application needs every occurrence, including overlaps, it can continue from one position after each hit rather than returning immediately.

Small assertions provide a quick sanity check before using the function on larger data. A brute-force matcher is still valuable as a test oracle because it makes expected results easy to state.

Complexity, testing and edge cases

Let n be the text length, m the pattern length and σ the alphabet size. A canonical implementation builds the bad-character table and good-suffix table in O(m + σ) time with fixed arrays, or O(m) expected time with a dictionary, and performs the combined search in O(n + m) worst-case time. Its auxiliary space is O(m + σ), reducible to O(m) for a dictionary containing distinct pattern characters.

The reference helper above performs slice comparisons while constructing the good-suffix table, so its preprocessing can take O(m³) in the worst case and is intended for clarity. A production implementation should use a linear-time good-suffix construction. The bad-character-only variant avoids that table but has O(nm) worst-case search time. It can still outperform a naïve scan when long stretches are skipped.

Choose according to the workload rather than the algorithm’s reputation. Python’s native str.find and regular-expression tools are normally faster and easier to maintain, while KMP offers predictable O(n + m) scanning. Boyer-Moore remains valuable for understanding skip logic, for small implementations with controlled character sets, and for embedded or educational settings where transparent behaviour matters.

Boundary behaviour should be explicit: this code defines an empty pattern as a match at zero, returns -1 when the pattern is longer than the text, and is case-sensitive. Unicode normalisation, CRLF line endings and overlapping matches are application decisions rather than hidden details. To study a different kind of non-linear rearrangement, the pancake sorting guide explains how prefix flips can reduce a permutation to sorted order.

Where this fits in Australia

In Sydney and Melbourne, fintech and online retail businesses handle payment descriptions, delivery updates, fraud alerts and support chats. A Python service may need to identify a known marker in these streams before passing the text onward. Boyer-Moore can work well for small buffers where building an index would add more overhead than it saves.

Brisbane property and tourism platforms can search listing descriptions, while Perth and Adelaide mining and logistics operations process manifests, maintenance notes and incident reports. Many teams serving these markets are small specialist operations with remote deployments, so a dependency-light algorithm with predictable memory use can be valuable. The text may contain vendor abbreviations and inconsistent line endings, which need deliberate normalisation.

Australian English also affects real test data: colour, organise and behaviour are normal spellings. People may search using colloquial expressions such as arvo for afternoon or come in at the coal for getting to the point, while cricket commentary supplies phrases such as not out and bowled. A case-insensitive matcher can help, but the application should state when normalisation occurs and which spelling variants it accepts.

Recommendations for dependable use

A dependable Boyer-Moore implementation needs explicit contracts and evidence rather than trust in a large skip table. These recommendations suit both a teaching exercise and production code.

• Define whether the caller wants the leftmost match, every match or overlapping matches, and document the empty-pattern behaviour.
• Use the platform’s native search for ordinary application work; reserve a hand-written algorithm for learning or a measured bottleneck.
• Precompute pattern tables once when the same needle is applied repeatedly, and reuse the immutable results safely.
• Compare results with a brute-force matcher across random strings, repeated characters, empty inputs and patterns near the text boundaries.
• Measure realistic Unicode, Australian English spellings, punctuation and line endings rather than clean ASCII samples.
• Keep case folding, normalisation and overlap rules in the API contract so identical inputs always produce identical results.

hello ML keeps community topic leads and corrections open through hello ML contact. Clear examples, measured claims and reproducible code help readers turn a classic matching method into software they can trust.