Naive pattern search
easyAfter matching four characters and failing on the fifth, it throws away everything it learned. Every faster matcher is a different answer to 'how do we keep that?'
O(n)Average O(n)Worst O(n·m)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How naive pattern search works
Line the pattern up under the text at offset 0 and compare left to right. On the first mismatch, slide the whole pattern one place right and start comparing again from its first character. That is the entire algorithm - two nested loops, no preprocessing, no extra memory. Each of the n - m + 1 alignments is tested independently of every other.
The cost hides in what it forgets. After matching four characters and failing on the fifth, the next alignment starts from scratch, re-reading text characters the previous alignment already saw. Search for aaab in a long run of a's and every alignment matches three characters before failing - that is the O(n·m) worst case, and DNA fragments and log data reach it regularly.
It is still often the right tool. On ordinary text most alignments fail on their very first comparison, so the observed cost sits near O(n) with a tiny constant, zero preprocessing, and O(1) space. Standard-library substring searches typically start with exactly this loop and only escalate for long patterns. Reach for it when patterns are short and inputs are not adversarial.
Step by step
- Search for aab in aaaab. With n = 5 and m = 3, there are three alignments to try, at offsets 0, 1, and 2.
- Alignment 0: text[0] and text[1] both match a. Then text[2] is a but pattern[2] is b - a mismatch after two good characters.
- Slide one place right and forget both matches. Alignment 1 repeats the story: two a's match, then text[3] fails against the pattern's b.
- Alignment 2: text[2], text[3], text[4] match a, a, b in turn. j reaches 3 = m, so report a hit at index 2.
- The run cost 9 character comparisons for a text of 5 - each alignment paid nearly the full m because the text is one long run of a's.
- KMP finishes the same search without ever re-reading a text character - the re-reads in alignments 1 and 2 are exactly what its failure function eliminates.
Complexity
| Best case time | O(n) |
|---|---|
| Average time | O(n) |
| Worst case time | O(n·m) |
| Space | O(1) |
Reference implementation
Python
def naive_search(text, pattern):
n, m = len(text), len(pattern)
hits = []
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
if j == m:
hits.append(i)
# a mismatch throws away everything we just learned
return hitsJavaScript
function naiveSearch(text, pattern) {
const n = text.length, m = pattern.length, hits = [];
for (let i = 0; i <= n - m; i++) {
let j = 0;
while (j < m && text[i + j] === pattern[j]) j++;
if (j === m) hits.push(i);
}
return hits;
}Worth noticing
It forgets everything on every mismatch
After matching four characters and failing on the fifth, the naive matcher slides one place right and starts from scratch - re-reading characters it has already seen. Every faster algorithm here is a different answer to 'how do we keep what we learned?'
O(n·m) worst case, and it is reachable
Search for 'aaab' in a long run of a's: every alignment matches three characters before failing. That is exactly the pathological input, and it is common in DNA and log data.
But it is often the right choice anyway
For short patterns on ordinary text, mismatches usually happen on the first character, so the real cost is close to O(n) with a tiny constant and no preprocessing. Most standard-library `indexOf` implementations start here.
Common pitfalls
- Looping i up to n instead of n - m lets the window run past the end of the text - an index error in some languages, silently wrong answers in others.
- Returning after the first hit when the task wants every occurrence. This version collects all matches in one pass; check which one the problem actually asks for.
- Treating the worst case as theoretical. Repetitive inputs - DNA fragments, log lines, runs of one character - reach O(n·m) in practice, not just in analysis.
- Comparing windows with slicing, like text[i:i+m] == pattern. It reads the same but allocates an m-character copy per alignment in Python, hiding real cost inside clean-looking code.
Where it is used
- The starting point of most standard-library substring searches - indexOf implementations typically run exactly this loop for short patterns.
- The interview baseline: write it first, then justify KMP or Rabin-Karp by pointing at its wasted comparisons.
- Find-in-file over ordinary prose, where first-character mismatches keep the observed cost near O(n).
- The verification step inside Rabin-Karp is this exact comparison loop, run only when two hashes agree.
Frequently asked questions
What is the time and space complexity of naive pattern search?
Best and average case O(n), worst case O(n·m), with O(1) extra space. On ordinary text most alignments fail on their first comparison, which is where the near-linear average comes from. The worst case needs long partial matches at almost every alignment - searching aaab in a long run of a's is the standard example.
Why is naive string matching slow on repetitive text?
Because a mismatch throws away everything the alignment learned. After matching k characters and failing, the next alignment re-reads k - 1 of the same text characters. Repetitive text makes k large at every offset, so nearly every character of the text ends up read close to m times.
Is the naive algorithm ever the right choice?
Often. It needs no preprocessing, no extra memory, and has a tiny constant factor, so for short patterns on non-adversarial text it beats the clever algorithms in practice. Standard libraries start here and only switch strategies for long patterns or repeated searches over the same text.
What is the difference between naive matching and KMP?
KMP spends O(m) preprocessing to build a failure function so its text pointer never moves backwards, guaranteeing O(n + m) overall. The naive matcher spends nothing up front and re-reads text instead - same answers, different bet about how often long partial matches occur in your data.