StringsAlgorithmaka brute-force matching, sliding comparison

Naive String Matching

Try every alignment of the pattern against the text and compare character by character.

▶ VisualizePattern: Sliding WindowPractice (1)
Progress

Overview

Naive matching finds every occurrence of a pattern p (length m) inside a text t (length n) by placing p at each of the n - m + 1 possible start positions and comparing left to right until a mismatch or a full match.

It is the baseline every other string-matching algorithm is measured against. In practice it is surprisingly competitive on natural-language text, because a random alignment usually fails on the first or second character. Its worst case, O(nm), appears on highly repetitive inputs such as t = "aaaa…a" and p = "aaa…ab".

pattern matchingbrute forceO(nm)baseline

Intuition

A mental model before the formal terms.

Imagine a stencil of the pattern that you slide along the text one cell at a time. At each stop you read the letters through the stencil from left to right; the moment one letter disagrees you stop reading and slide the stencil one cell further. The stencil has no memory — after a failure it forgets everything it just saw, which is exactly the inefficiency Knuth–Morris–Pratt (KMP) removes.

How it works

  1. For each start index i from 0 to n - m, set j = 0.
  2. While j < m and t[i + j] == p[j], increment j.
  3. If j reached m, report a match at i. Otherwise (or after reporting) continue with i + 1.
  4. The scan at a given i can stop early at the first mismatch, which is why the average case on non-repetitive text is close to O(n).

Why it works

Every occurrence of p in t starts at some index i ≤ n - m, and the inner loop at that i checks exactly the characters t[i..i+m-1] against p[0..m-1]. Since all start positions are tried, no occurrence can be missed and no false match can be reported.

The cost bound is (n - m + 1) · m comparisons. On random text over an alphabet of size σ the expected comparisons per alignment is below 1/(1 - 1/σ), i.e. about 1.04 for the Latin alphabet, so the expected total is roughly n.

Recognition

How to tell a problem wants this.

  • The pattern is short (m ≤ 10) or the text is small enough that n · m is a few million operations.
  • You need a correct answer quickly in an interview before optimising — write this first, then discuss Knuth–Morris–Pratt (KMP) or Rabin–Karp.
  • Inputs are natural language or otherwise non-repetitive, so worst-case behaviour will not occur.
“contiguous subarray” → Sliding Window

Interactive visualization

Play, step, change the input. ← → and space work too.

a
a
0
b
1
x
2
a
3
b
4
c
5
a
6
b
7
c
8
a
9
b
10
y
11
pattern
a
0
b
1
c
2
a
3
b
4
y
5
1/35Try every alignment s of the pattern (length 6) against the text (length 12); there are 7 of them.
Characters being comparedMatchMismatch at this alignment
PseudocodeLearn Naive String Matching →
1for s in 0 .. n-m:
2  j = 0
3  while j < m and text[s+j] == pattern[j]:
4    j += 1
5  if j == m: report match at s
6return matches
Variables
n12
m6
Complexity
best O(n)
avg O(n + m)
worst O(n · m)
space O(1)
Speed

Pseudocode

1for i in 0 .. n - m:
2  j = 0
3  while j < m and t[i + j] == p[j]:
4    j += 1
5  if j == m: report match at i

Implementations

1def naive_search(text: str, pattern: str) -> list[int]:
21 · Handle edge cases
3    n, m = len(text), len(pattern)
4    matches: list[int] = []
5    if m == 0:
6        return list(range(n + 1))
72 · Try every alignment
8    for i in range(n - m + 1):
93 · Compare characters left to right
10        j = 0
11        while j < m and text[i + j] == pattern[j]:
12            j += 1
134 · Record a full match
14        if j == m:
15            matches.append(i)
16    return matches
Walkthrough
  1. range(n - m + 1) produces exactly the valid start positions; when m > n the range is empty and the function returns [] without any special case.
  2. The empty pattern returns list(range(n + 1)) — every position, matching the convention of str.find("").
  3. text[i + j] == pattern[j] compares single-character strings; Python interns short strings so this is cheap, but still slower than a C loop.
  4. j == m after the while means the full pattern matched at i.
Complexity (this implementation)
time O(n · m) worst, ~O(n) average · space O(1) extra (output excluded)

A per-character Python loop is roughly 50–100× slower than str.find, which runs the same idea in C.

Language notes
  • str.find(pattern, start) and the in operator implement substring search in C (a two-way / Crochemore–Perrin variant since 3.10), so prefer them outside of an interview.
  • Python strings are immutable sequences of Unicode code points; len counts code points, so surrogate pairs are not an issue as they are in JS.
  • Slicing text[i:i + m] == pattern copies m characters each time — fine for small m, but it is an O(m) allocation per alignment.
Common mistakes in this language
  • Using range(n - m) (missing the + 1) and dropping a match that ends exactly at the last character.
  • Comparing text[i + j] without the j < m guard first — and short-circuits, so the order of the two conditions matters.
  • Returning after the first match when all occurrences are requested.
Language differences that matter here
  • String length: Python len counts Unicode code points; JS/TS .length counts UTF-16 code units; C++ std::string::size() counts bytes. Alignments can split a multi-byte or surrogate-pair character in C++ and JS/TS.
  • C++ size_t is unsigned: text.size() - pattern.size() wraps when the pattern is longer, so cast to int or write the bound as i + m <= n.
  • Out-of-range access is undefined behaviour in C++ (operator[]), returns NaN from charCodeAt in JS/TS, and raises IndexError in Python.
  • Every language ships a C-level substring search (std::string::find, indexOf, str.find) that should be used outside interviews.

Complexity

Best
O(n)
Average
O(n + m)
Worst
O(n · m)
Space
O(1)

Average assumes non-repetitive text; worst case is repetitive text like "aaaa…a" vs "aa…ab".

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Short patterns or small texts where n · m is cheap.
  • Natural-language text where mismatches happen within one or two characters.
  • As a correctness oracle when testing a faster matcher.
Avoid it when

Alternatives

Knuth–Morris–Pratt (KMP)Rabin–KarpZ-AlgorithmAho–Corasick

Common mistakes

  • Looping i to n - 1 instead of n - m and reading past the end of the text.
  • Forgetting the empty-pattern case (matches at every position by convention).
  • Restarting the inner comparison from i + 1 after a full match but then also skipping m characters — overlapping matches like "aa" in "aaa" would be lost.

Interview patterns

  • strStr / indexOf: return the first occurrence — naive is accepted, but be ready to explain KMP.
  • Counting occurrences of a short word in a long text.
  • Baseline for "is t a rotation of s?" by searching t inside s + s.
Interview questions on this
Mock interviews

Example problems

Find the Index of the First Occurrenceeasy