Why naive matching wastes work
A naive search slides a pattern one step at a time and rechecks characters it already compared. The Knuth Morris Pratt algorithm removes that waste by precomputing how far the pattern can shift after a mismatch, so the text pointer never moves backward.
The failure function
For each position in the pattern, the failure function records the length of the longest proper prefix that is also a suffix of the part seen so far. This number tells us the next pattern position to try after a mismatch, because the matched prefix is already known to align.
- Build it by comparing the pattern against itself.
- A longer border means we can resume deeper into the pattern.
- A border of zero means we restart the pattern from the beginning.
Matching with it
Scan the text once. On a match, advance both pointers. On a mismatch, fall back in the pattern using the failure function instead of restarting. The text pointer only ever moves forward, so the whole scan is linear in the combined lengths.
Key idea
Precompute the longest prefix that is also a suffix at each spot so a mismatch shifts the pattern smartly and the text is scanned only once.