Naïve String Matching

Slide the pattern across the text and compare straight through at every shift — no setup, O(n·m) worst case.

Naïve string matching is the most direct way to find a pattern inside a longer text: line the pattern up at the very first position, compare character by character, and on any mismatch slide the pattern one place to the right and start the comparison over from the beginning. It needs zero preprocessing — which is exactly why it can waste so much work.

The slide-and-compare loop

1Place the pattern at shift s = 0 (aligned with the start of the text).
2Compare pattern[0], pattern[1], … against the text at that shift.
3If every character matches → report a hit at s.
4On the first mismatch, abandon this alignment, set s = s + 1, and restart comparing from pattern[0].
5Stop once the pattern would run off the end of the text (s > n - m).

function naiveSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  const hits = [];
  for (let s = 0; s <= n - m; s++) {  // every shift
    let j = 0;
    while (j < m && text[s + j] === pattern[j]) j++;
    if (j === m) hits.push(s);         // full match at s
  }
  return hits;
}

A worked example — and the waste

Search AAAAB for the pattern AAAB. At shift 0 it matches A, A, A, then hits a mismatch (A vs B) at the fourth character. It shifts by one and at shift 1 re-compares those same As all over again, mismatches again, and so on. Three of the four characters it just verified get re-read on the next shift — that repeated re-checking is the whole inefficiency.

Where O(n·m) bites

The worst case is a text and pattern that *almost* match everywhere — like text AAAA…A with pattern AAA…AB. Every shift compares nearly the whole pattern before failing on the last character, giving roughly n × m comparisons.

Why anyone still uses it

On ordinary text, mismatches usually happen on the *first* character, so most shifts cost O(1) and the real-world running time is close to O(n). With no table to build, it is often the fastest choice for short patterns or one-off searches. KMP, Rabin-Karp, and the DFA method all exist to kill the worst case the naïve method leaves on the table.

OperationTimeSpace

Worst case · n = text length, m = pattern lengthO(n·m)O(1)

Typical text · most shifts fail on the first char≈ O(n)O(1)

Check yourself

What makes naïve matching slow in the worst case?