Brute force is the starting point for any pattern-matching problem. The specific way it wastes work is what motivates every faster algorithm.

This chapter implements brute force, traces it on a worst-case input, and identifies the redundant comparisons that KMP eliminates.

For each starting position i in the text, compare T[i..i+m-1] with P character by character. If all m characters match, record the position. On any mismatch, advance i by one and try again.

There are n - m + 1 starting positions to try.

The number of positions to check is n - m + 1. Position 0 starts at the beginning of the text; position n - m is the last where the pattern fits without running off the end.

Two versions: find the first occurrence, and find all occurrences.

Finding the First Occurrence

This is the version that finds the index of the first occurrence of the pattern in the text. For each valid starting position, compare characters one by one. Return the position on a full match, -1 if no position matches.

Finding All Occurrences

For every match position rather than just the first, record on match and keep going instead of returning.

The "find all" version handles overlapping matches because the outer loop advances by 1, not by m. The distinction matters whenever a pattern overlaps with itself.

Which behavior is correct depends on the problem. A first-occurrence search returns once and stops. Problems that count all overlapping occurrences want i += 1. Some text-processing tools (replacing or highlighting) want non-overlapping matches and need i += m. Read the problem statement before choosing.

Text: ABCABCABD (n = 9) Pattern: ABCABD (m = 6)

Four valid starting positions: i = 0 through i = 3.

Position i = 0:

The first five characters match. The sixth is 'C' in the text vs 'D' in the pattern, so the algorithm shifts the pattern one position to the right.

Position i = 1:

First comparison fails: 'B' != 'A'. Shift right.

Position i = 2:

First character fails: 'C' != 'A'. Shift right.

Position i = 3:

All characters match. Pattern found at position 3.

Total comparisons: 6 + 1 + 1 + 6 = 14. At position i = 0, the first five characters of the pattern matched the text. Those text characters are text[3..7] = "ABCAB", which get compared again at position i = 3. The same five comparisons happen twice. On this input the waste is small; on highly repetitive text it dominates the runtime.

Worst Case Example:

At every position, the first three characters of the pattern match (all 'A's), and the mismatch only happens at the last character of the pattern ('B' vs 'A'). Tracing a few positions:

Position i = 0:

Position i = 1:

Position i = 2 through i = 4: The same thing happens. Three matches followed by a mismatch.

Position i = 5:

Positions 0 through 4 each perform 4 comparisons. Position 5 also performs 4. That is 6 positions × 4 comparisons = 24 total. In general, this worst case performs about (n - m + 1) * m comparisons.

For n = 1,000,000 and m = 1,000, that is roughly one billion comparisons. This is the O(n*m) worst case.

Despite the O(n*m) worst case, brute force is the right choice in many situations:

Brute force is the wrong choice only for long patterns on highly repetitive text, or when search is on a latency-critical path.

The worst case needs two ingredients:

After a mismatch, brute force discards the comparisons it just made. At position i = 0 in the earlier walkthrough, the comparisons revealed text[0..4] = "ABCAB". Text[3..4] = "AB" is the same as the start of the pattern, so when search moves to position i = 3 the first two characters are guaranteed to match. Brute force compares them from scratch anyway.

A smarter algorithm uses information from previously-matched text to (a) skip positions that cannot match, and (b) at the next valid position, skip characters already known to match.

KMP preprocesses the pattern so that for every possible mismatch position it knows exactly how far the pattern can shift without missing a valid alignment. The result is an algorithm that never re-examines a text character it has already compared, bringing the worst case down to O(n+m).

Time Complexity:

Best case: the first character of the pattern rarely appears in the text. Searching for "ZEBRA" in English text fails almost every position at the first comparison because 'Z' is uncommon.

Average case on random text over alphabet size σ: expected comparisons per position are about σ/(σ-1), which is roughly 1.04 for the English alphabet. Total expected comparisons ≈ 1.04n.

Worst case: inputs like T = "AAA...AB" and P = "AA...AB" where every mismatch happens at the last character of the pattern.

Space Complexity: O(1) auxiliary. The output list for "find all" is O(k) where k is the number of matches, but that is output, not auxiliary.