Brute-Force Pattern Matching

Graph algorithms worked on data with connections between elements. This topic moves to a different structure: sequences of symbols in order — text.

The basic question of text processing is pattern matching, and this lesson builds the question itself along with its plainest solution. The next four lessons improve on the same problem with different ideas; the measure stays the same throughout: the number of character comparisons.

The Problem

Pattern matching: A text of length $n$ and a pattern of length $m$ are given; the positions at which the pattern occurs in the text are wanted.

The question has three common forms, and their costs differ:

• First occurrence. Stop as soon as one is found.
• All occurrences. Continue to the end of the text.
• Occurrence count. Count without storing positions.

The same text and pattern are used throughout this topic:

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"

The pattern occurs once in the text, at index 10. The example is also well suited for testing the ideas of the following lessons, because the pattern itself contains internal repetition.

The Sliding Scan

The plainest solution is to place the pattern at every position of the text and compare it character by character. On a mismatch, the pattern is shifted one position to the right and comparison restarts from scratch.

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


print(brute_force(text, pattern))        # ([10], 29)
print(brute_force("ABABAB", "AB"))       # ([0, 2, 4], 8)

The invariant is this: no position before shift contains a full match. Termination follows from the shift increasing by one on every turn.

The algorithm is correct and uses no extra space. Its problem is its cost.

Cost

The outer loop runs $n - m + 1$ times, the inner loop at most $m$ times:

$$O\big((n - m + 1)\, m\big) = O(nm)$$

Reaching the worst case requires an input where a long prefix matches on every shift but the end does not.

bad_text = "A" * 30 + "B"
bad_pattern = "A" * 10 + "B"

print(brute_force(bad_text, bad_pattern))     # ([20], 231)
print(len(bad_text), len(bad_pattern))        # 31 11

On every shift, ten A characters match, the final character does not, and all the work is wasted. The comparison count approaches the product $(n - m + 1) \cdot m$: $21 \times 11 = 231$.

Such inputs look artificial, but binary data, sequences over a small alphabet (genetic sequences, for instance), and logs carrying repetitive structure genuinely produce this behavior.

Behavior on Real Text

Natural language behaves differently: a mismatch typically shows up within the first few characters, and the inner loop breaks early.

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", "cost", "zzz"):
    positions, count = brute_force(long_text, query)
    print(query, len(positions), count, len(long_text))

# pattern 10 1144 1060
# cost 10 1097 1060
# zzz 0 1058 1060

The comparison count is a small multiple of the text length — nowhere near the multiplicative worst case. With an alphabet of size $\sigma$, the expected comparison count per shift is approximately $1/(1 - 1/\sigma)$; this value approaches 1 as the alphabet grows.

The result echoes a warning from the algorithm-analysis lessons: worst case and typical case are different questions. Brute-force search is fast in practice on text with a large alphabet; what makes it a problem is that it silently drops to quadratic behavior on adversarial input.

The Unit of Comparison

Algorithms are defined over “characters,” but in real text what that unit is turns out to be a choice, and the choice changes the result.

The encoding lesson in the How Computers Work course separated three levels: the byte, the code point, and the grapheme cluster — the unit the user counts as a single letter. A pattern-matching routine has to state which of these it operates on.

Byte-level search is the fastest, and it produces no false matches in multibyte encodings — the encoding guarantees that one character’s bytes never appear in the middle of another character’s bytes. The position found, however, is in bytes; a character position requires a conversion.

Code-point-level search causes surprises with combined letters: two pieces of text that look identical can be written with different code-point sequences. In that case a normalization step is needed before the search.

Case-insensitive search, in turn, depends on the language; case-folding rules are not the same in every language, and a single-character conversion is not guaranteed to always produce a single character.

These distinctions do not change the algorithm, but they determine the cost and the correctness of the comparison operation. In this lesson and the following ones, the unit of comparison is taken to be a single code unit.

The Information That Is Lost

The algorithm’s waste concentrates in a single point: the comparisons made before a mismatch are forgotten.

When comparing the pattern ABABC against the text ABABD…, it is known that the first four characters matched. Brute force discards this and restarts one position to the right — even though the structure of the matched part could show that trying some of the shifts is unnecessary.

The next three lessons use this information in three different ways:

Approach	Information used
Rabin–Karp	The hash value of the window; comparing numbers instead of characters
Knuth–Morris–Pratt	The pattern’s own prefix–suffix structure
Boyer–Moore	The mismatched text character and matching from the end of the pattern

All three solve the same problem and produce the same result; what separates them is which information they precompute and use during the search.

When It Is Enough

Brute-force search has two advantages: it does no preprocessing and uses no extra space. This makes it the right choice when:

• The pattern is short and the text is small; setup cost outweighs the gain.
• Every search uses a different pattern; preprocessing would have to be paid again each time.
• The alphabet is large and the text is natural language; typical behavior is already close to linear.

By contrast, if the same pattern will be searched for many times, preprocessing methods stand out; if the same text will be queried many times, structures that preprocess the text do. This second path is the subject of the suffix-arrays lesson.

Summary

• Pattern matching finds the positions at which a given sequence occurs in a text; first occurrence, all occurrences, and counting have different costs.
• Brute-force search compares from scratch on every shift; it uses no extra space and needs no preprocessing.
• The worst case is $O(nm)$ and genuinely occurs on repetitive inputs over a small alphabet.
• Because mismatches occur early in natural language, typical cost is close to linear.
• The algorithm’s waste is discarding the information gained before a mismatch.
• The following methods use this information through a hash value, the pattern’s prefix–suffix structure, or matching from the end.

Next Step

The first improvement idea is surprising: never compare characters at all. If every window of the text is reduced to a number and compared against the pattern’s number, most positions are eliminated in a single operation. The next lesson builds the rolling hash idea, updated at constant cost from window to window, and how hash collisions are handled.