Naive Pattern Matching

Ctrl+F, grep, str.find: finding a pattern inside a text is one of the most common things programs do. Start with the obvious method, so you can see exactly where it wastes time.

beginner⏱ 8 min read

←Builds on

0Big-O & Growth RatesCounting comparisons gives O(n·m) and shows where the work is wasted.1Prefix Sums, Two Pointers & Sliding WindowThe naive matcher slides a window of length m across the text.

Leads to→

11Rolling Hash & Rabin–KarpRabin–Karp keeps the sliding window but compares fingerprints before characters.11Prefix Function & KMPKMP removes the naive matcher's habit of stepping back in the text.+Manacher's AlgorithmIt starts from expanding around every center, the naive O(n²) idea, and removes the waste.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Try every shift

You have a text T of length n and a pattern P of length m. The naive matcher places P under T at shift s = 0, compares characters left to right, and stops at the first mismatch. Then it moves the pattern one position right and starts again from the pattern's first character.

If all m characters match, s is an occurrence. The last useful shift is n − m, because after that the pattern would hang off the end of the text.

In code it is two nested loops, about five lines. That is its strength: easy to write, easy to get right, and often fast enough.

Each row is one shift. Green = matched, red = first mismatch, grey = never compared.

02The worst case: n·m

On ordinary text most shifts die on the first or second character, so the naive method runs in about O(n). The trouble is inputs where almost the whole pattern matches at every shift.

Take T = AAAAAAAAAA and P = AAAB. At every one of the n − m + 1 shifts, three As match and only the B fails. That is m comparisons per shift, so the total is (n − m + 1)·m, which is O(n·m).

With n = 10⁶ and m = 10³ that is about a billion comparisons. Repetitive data like DNA, logs or generated test cases hit this case for real.

03Where the work is wasted

Look at what happens after a mismatch at pattern position j. You just learned that T[s..s+j−1] equals P[0..j−1]: you know those j text characters. The naive method forgets all of it, moves one step, and reads most of them again.

The two smarter algorithms in this stage each fix this in a different way:

Rolling hash compares a whole window with one number comparison.
KMP uses what was already matched to decide how far it can safely jump, so it never moves back in the text.

Still, the naive matcher is a good default for short patterns, and it is the baseline you test faster code against.

Cost at a glance

Typical text≈ O(n)

Worst caseO(n·m)

Extra memoryO(1)

Remember

The naive matcher tries every shift and compares left to right until the first mismatch.
Its worst case is O(n·m), reached on repetitive inputs like AAAA…A with pattern AA…AB.
The waste is rereading text characters that were already matched; hashing and KMP remove it.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the comparison counter, and notice how often the pattern slides back over characters it has already seen.

Interactive visualizerfocus here, then space ← →

Naive pattern matching · comparisons: 0

AABAACAADAABAABA

AABA············

Search pattern "AABA" (length 4) in a text of length 16 by trying every shift.

Pseudocode

 1 for each shift s in text: 2   match pattern char by char 3   on the first mismatch, abandon this shift 4   if all chars matched → occurrence at s 5 // worst case O(n·m)

1 / 1

Check

Three questions. Pick an answer to see why.

Text length n = 12, pattern length m = 4. How many shifts does the naive matcher try?

Which input makes the naive matcher slowest?

At shift s, the first mismatch is at pattern position j = 3. What do you now know for sure?

Practice

Real problems to lock it in, easiest first.

LeetCodeFind the Index of the First Occurrence in a String beginner↗LeetCodeRotate String beginner↗LeetCodeRepeated Substring Pattern beginner↗CSESString Matching intermediate↗