The naive problem
To find a pattern inside a text, the naive method compares the pattern at every position and, on a mismatch, shifts by one and starts over. That rereads characters again and again, which is wasteful.
The failure function
Knuth Morris Pratt precomputes a table over the pattern alone. For each prefix it records the length of the longest proper prefix that is also a suffix of that prefix. This table is the failure function, sometimes called the partial match table.
- It depends only on the pattern, not the text.
- It answers: after a mismatch, how much of what we matched is still usable.
How the search runs
We scan the text once with a pointer that never moves backward. When characters match, both pointers advance. On a mismatch, instead of restarting, we consult the failure table and jump the pattern pointer to the longest reusable border.
- The text pointer only moves forward.
- Already matched characters are never recompared.
Why it is fast
Because the text is read in a single forward pass and the pattern pointer only retreats along borders it already verified, the total work is linear in the combined length of text and pattern.
Key idea
KMP precomputes longest prefix suffix borders of the pattern so a mismatch shifts forward intelligently, letting the text be scanned in one linear pass.