Naive matching and KMP

Find a pattern in a text without ever backing up the text pointer. Speed from a precomputed failure table.

A mismatch is information

• Naive search: on mismatch, slide by 1 and re-read → O(n·m)
• The matched chars are a known prefix of the pattern
• If that prefix overlaps its own suffix, slide by more than 1
• Text pointer never rewinds → O(n+m)

The failure function

• lps[i] = longest proper prefix of pattern[:i+1] that is also a suffix
• Built in O(m) by matching the pattern against ITSELF
• On mismatch after j matches → resume as if lps[j−1] matched
• lps("ababc") = [0,0,1,2,0]

Watch the pattern slide

Blue = comparing · green = matched · red = mismatch. After abab fails, the pattern jumps forward — no rewind.

Linear vs quadratic

aaaa…a vs aaaa…b: naive 398K comparisons, KMP 16K → 25× fewer.

Takeaway

Naive isn't wrong — it's fragile (latent quadratic on repetitive input). KMP pays O(m) setup for a linear guarantee, whatever the input. Next: Rabin-Karp — compare numbers (rolling hash), not strings.