---
title: 'Brute-Force Pattern Matching'
source: 'https://academia.sh/en/courses/algorithms/brute-force-pattern-matching'
course: Algorithms
language: en
updated: '2026-08-17T18:07:46+00:00'
license: 'CC BY-SA 4.0'
---

# Brute-Force Pattern Matching

The definition of pattern matching in text, the sliding scan, character-comparison count, worst-case inputs, and behavior on real text.

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:

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

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

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

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