the Knuth-Morris-Pratt algorithm
/ kuh-NOOTH MOR-iss PRATT /
When naive matching fails partway through a comparison, it slides the pattern forward by just one and forgets everything it learned. But think about it: you have just read several text characters and they matched the start of your pattern. That is real, hard-won information about the text. KMP's whole idea is to keep that information and use it to slide the pattern forward by more than one whenever it safely can, so it never has to re-read a text character it already consumed.
Here is how it works. KMP first builds, from the pattern alone, a prefix (failure) function that answers: if I have matched the first k characters of the pattern and the next one fails, what is the longest pattern-prefix that is also a suffix of what I just matched? That number tells KMP exactly how far it can shift the pattern without skipping any possible match. Then it scans the text left to right with a single pointer that never moves backward: on a match it advances both pattern and text pointers; on a mismatch it consults the failure function to retreat the pattern pointer (not the text pointer) to the next promising position, and continues. Because the text pointer only ever moves forward and the pattern pointer's total backward movement is bounded, the scan is O(n), and building the failure function is O(m), for a total of O(n+m).
KMP, published in 1977 by Donald Knuth, James Morris, and Vaughan Pratt, was the first matching algorithm to guarantee linear time in the worst case, and it remains a cornerstone. Its lasting lesson is bigger than string search: preprocess the pattern to learn its internal self-overlaps, then exploit those during the scan so failed work is never wasted. The same failure-function idea generalizes to multiple patterns (Aho-Corasick) and underlies many later string algorithms. Note that KMP guarantees linear time always, whereas Boyer-Moore is often faster in practice but without KMP's clean worst-case promise.
P = "abcab", T = "abcabd...". We match a,b,c,a,b (5 chars) then the next text char d fails against P's 'c'. Naive would restart at text position 1. KMP knows the matched suffix "ab" equals a pattern prefix, so it shifts the pattern to realign that "ab" and resumes comparing from P[2] — the text pointer never went backward, no character is re-read.
On mismatch, KMP shifts the pattern (via the failure function) instead of resetting the text pointer.
The text pointer in KMP never moves backward — that single fact is what buys O(n+m). A common confusion: KMP's speedup comes entirely from the pattern's self-structure, so it cannot 'skip ahead' in the text the way Boyer-Moore can; it only avoids re-reading.