Naive String Matching: Brute-Force Pattern Search

The naive string matching algorithm finds a pattern in a text the way you would by hand: put the pattern under the text at position 0, compare character by character, and on the first mismatch slide it one place right and start again. It is the baseline every faster algorithm is measured against, and it is better than its reputation: on most real text it is close to linear. This article counts its comparisons exactly, builds the input that makes it slow, and shows the piece of information it throws away, which is where KMP begins.

The problem it solves

Given a text of length n and a pattern of length m, report every index where the pattern starts. Overlapping matches count: "aa" occurs three times in "aaaa", at 0, 1 and 2.

The brute force follows from the definition. There are n - m + 1 places the pattern could start. Try each one and compare up to m characters, stopping at the first difference. No preprocessing, no extra memory, nothing to get subtly wrong, which is why it is also the reference implementation you test cleverer matchers against.

The intuition

The cost depends entirely on how long each attempt survives before its first mismatch.

• Random-looking text: most attempts die on the first or second character. Over an alphabet of σ equally likely letters, an attempt reaches its second comparison with probability 1/σ, its third with 1/σ², and so on, so it averages fewer than σ / (σ - 1) comparisons. For DNA's four letters that is under 1.33 per position, effectively linear.
• Repetitive text: a text of a thousand as and the pattern aaaaaaaaab survive nine comparisons at every alignment before the b fails. That is (n - m + 1) × m comparisons, the O(n·m) worst case.

The waste in the worst case is specific. After an attempt matches several characters and then fails, the algorithm knows what those text characters are: they equal the pattern's prefix. Sliding by one and re-reading them ignores that knowledge. If the matched part of the pattern ends with a copy of its own beginning, the pattern can jump straight to that overlap and keep the characters already matched. Precomputing those overlaps is the KMP failure table; the Z algorithm and Rabin-Karp are other routes to avoiding the re-reads.

Watch it run

The animation searches for ababc inside abababc, starting with the pattern aligned at index 0. Four characters match, and then c meets a at index 4. The naive fix is to slide one step right. Sliding by one throws away four known characters and immediately fails: b is not a.

But the mismatch told us something. For each prefix, store the longest prefix that is also a suffix. For abab that overlap is 2: the ab at the front is also the ab at the back. So on a mismatch after four matches, fall back to table[3] = 2 and shift the pattern by two, not by one. The kept ab is already correct, so the scan resumes at index 4, and the text pointer never moved back. Then b, then c: a match at index 2, having read every character of the text exactly once. The naive version gets the same answer, but spends 11 comparisons on it, as the code below counts.

The code

The naive matcher, returning every start index and the number of character comparisons it made:

import random

def naive_find_all(text, pat):
    """Every start index of pat in text, and the character comparisons it took."""
    n, m = len(text), len(pat)
    hits, comparisons = [], 0
    for s in range(n - m + 1):            # every alignment, left to right
        j = 0
        while j < m:
            comparisons += 1
            if text[s + j] != pat[j]:
                break                     # first mismatch: give up on this alignment
            j += 1
        if j == m:
            hits.append(s)
    return hits, comparisons

print(naive_find_all("abababc", "ababc"))     # ([2], 11)
print(naive_find_all("aaaa", "aa"))           # ([0, 1, 2], 6)
print("aaaa".count("aa"))                     # 2  -> count() skips overlaps

# The worst case: every alignment matches m - 1 characters, then fails
text, pat = "a" * 1000, "a" * 9 + "b"
print(naive_find_all(text, pat)[1], (1000 - 10 + 1) * 10)   # 9910 9910

# Random text: the first comparison usually fails, so the scan is near-linear
rng = random.Random(39)
dna = "".join(rng.choice("acgt") for _ in range(100_000))
hits, comparisons = naive_find_all(dna, "gattacag")
print(len(hits), round(comparisons / (len(dna) - 7), 2))   # 3 1.33

11 comparisons for the animation's example: 5 at alignment 0, 1 at alignment 1, 5 for the match at 2. The worst case hits its formula exactly, and the random DNA lands on the predicted 1.33 per position.

The same search with the lesson's failure table, for contrast, and the seeded check: on 3,000 random texts and patterns over a two-letter alphabet, where long partial matches are common, both matchers must agree with a slicing brute force, the first hit must equal str.find, the naive count must stay within (n - m + 1) × m, and KMP must stay within 2n:

def failure(pat):                          # the lesson's table
    table, k = [0] * len(pat), 0
    for i in range(1, len(pat)):
        while k and pat[i] != pat[k]:
            k = table[k - 1]
        if pat[i] == pat[k]:
            k += 1
        table[i] = k
    return table

def kmp_find_all(text, pat):
    """Same answer, but a mismatch falls back in the pattern, never in the text."""
    table, hits, comparisons, k = failure(pat), [], 0, 0
    for i, ch in enumerate(text):
        while True:
            comparisons += 1
            if ch == pat[k]:
                k += 1
                break
            if k == 0:
                break
            k = table[k - 1]
        if k == len(pat):
            hits.append(i - k + 1)
            k = table[k - 1]
    return hits, comparisons

print(kmp_find_all("a" * 1000, "a" * 9 + "b")[1])   # 1991 -> under 2n, against 9910

rng = random.Random(39)
ok = True
for _ in range(3000):
    text = "".join(rng.choice("ab") for _ in range(rng.randint(0, 30)))
    pat = "".join(rng.choice("ab") for _ in range(rng.randint(1, 5)))
    n, m = len(text), len(pat)
    want = [s for s in range(n - m + 1) if text[s:s + m] == pat]   # brute force: slicing
    hits, naive_cost = naive_find_all(text, pat)
    kmp_hits, kmp_cost = kmp_find_all(text, pat)
    ok &= hits == kmp_hits == want
    ok &= (hits[0] if hits else -1) == text.find(pat)
    ok &= naive_cost <= max(0, n - m + 1) * m and kmp_cost <= 2 * n
print(ok)                                   # True

The complexity

• Worst case: O(n·m) time, reached on repetitive text and patterns.
• Typical case: close to O(n) on varied text, because attempts fail early.
• Space: O(1) beyond the output.

KMP's guarantee is O(n + m); the Big-O cheat sheet lists it. In CPython, str.find and in do not use the naive loop: they use a Boyer-Moore-Horspool style search, and since 3.10 a two-way algorithm for longer patterns that keeps the worst case linear (from memory, as of October 2026). Calling the built-in is almost always the right production choice.

Where it goes wrong

• Missing overlaps. str.count and re.findall with a plain pattern return non-overlapping matches; "aaaa".count("aa") is 2, not 3.
• The loop bound. The last alignment is n - m; range(n - m + 1) covers it, and a pattern longer than the text yields an empty range rather than an error.
• Slicing inside the loop. text[s:s + m] == pat is correct but copies m characters at every alignment, even when the first one differs.
• Assuming the worst case is typical. Logs and prose rarely trigger it; DNA and repetitive generated data can.

When it shows up in interviews

As "implement strStr" or "find the index of the first occurrence", where the brute force is the expected first answer, followed by "what is its worst case?" and "can you do better?", which leads into KMP, Z or rolling hashes. It also appears in reverse: counting overlapping occurrences, where count() is the trap.

How to say it in an interview

"The brute force tries every alignment, n minus m plus one of them, and compares until the first mismatch. On varied text attempts fail almost immediately, so it's close to linear, but on something like a run of a's with a pattern ending in b, every alignment does m comparisons: O(n·m). The waste is re-reading characters it already matched; KMP precomputes, for each prefix, the longest border, so on a mismatch the pattern shifts by the overlap and the text pointer never moves back, giving O(n + m)."