Pattern matching: the naive scan
The substring-search problem and the straightforward O(n·m) sliding approach. · 9 min read
The problem
Pattern matching asks: does a pattern P (length m) occur inside a text T (length n), and where? It's everywhere — search, find-and-replace, DNA matching, log scanning. A string is just an array of characters, so the array techniques you know apply.
The naive algorithm
Try every possible alignment: place P at each start index i of T, and compare characters left to right. On a mismatch, slide P one position right and start over.
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m && text[i + j] == pattern[j]) j++;
if (j == m) record_match(i);
}Interactive visualization: Naive matching: slide by one on a mismatch — step through it frame by frame on this page.
n − m + 1 alignments— Each start index of the pattern.up to m comparisons each— Worst case like "aaaa…" vs "aaab".(n − m + 1) · m— Multiply.
Result: O(n · m) worst case
Practice: Find the Index of First Match (Easy) — Return the first index where `needle` occurs in `haystack`.
Practice: Count Pattern Occurrences (Medium) — How many times does the pattern occur (overlaps allowed)?