The guide
A failure table lets the search skip ahead, and the text is never read twice
Why a mismatch tells the Knuth-Morris-Pratt search where to resume, why the text pointer never backs up, and what the table has to do with overlapping matches and counting comparisons.
- -1 0 0 0 -1 0 2 0 table T for ABCDABD, the one the search reads
- 15 where ABCDABD starts in the 23-character example text
- 27 of 46 loop iterations against the 2n bound on the example
- 175 and 55 comparisons for A^6 B in A^30 B: naive, then KMP
- 0 0 0 0 1 2 0 the classical prefix function of ABCDABD
Read the full guide Fold the guide
Searching for a word inside a long text sounds like a chore with only one sensible method: line the word up, compare letter by letter, and shift by one when it fails. That method works. It also throws away everything it learned. The Knuth-Morris-Pratt search keeps what it learned and uses it to skip ahead.
The search was conceived by James H. Morris, and Donald Knuth discovered it independently a few weeks later, starting from automata theory. Morris and Vaughan Pratt wrote it up as a technical report in 1970, and the three published it together in 1977. A similar linear-time method had been found by Matiyasevich in 1969.
What the naive search wastes
Take a text of 30 letters A followed by a B, and a word of six A’s and a B. The naive search tries the word at position 0. Six letters match, then the B meets an A and fails. It shifts by one and does the same again. Each failed start costs seven comparisons, and the 25 starts that fail cost 175 comparisons in all. The one match, at position 24, comes at the end.
Now notice what is wasted. After the failure at position 0 the search already knows the next six text letters are A’s, because it just read them. The word would fit again with one fewer match, yet the naive search re-reads those letters from scratch. On a million letters and a word of a thousand, the Wikipedia page for the algorithm counts about a billion comparisons for this shape of input.
The table the search reads
The word itself holds the answer. When the comparison fails at position k of the word, the letters just matched are the first k letters of the word, so the word already knows which of its own prefixes can still be alive. The partial-match table T records that. After a mismatch at position k the search resumes with the word index at T[k], and the text index stays exactly where it was.
For the word ABCDABD the table is -1 0 0 0 -1 0 2 0, with one more entry than the word has letters. The first entry, minus 1, means that if the very first letter fails there is nothing to reuse and the text index must move on. The entry at position 6 is 2: a mismatch after matching ABCDAB can resume with AB, which is still a live prefix.
The table has a second life. Where the next letters agree, the entry copies the earlier one, which skips a shift that would fail on the same character. That is why T carries minus 1 at position 4, where a plain longest-border rule would give 1.
Building the table, one position at a time
The table is built by running the same idea on the word against itself. Start with T[0] = -1 and a candidate border of length zero. For each position, compare its letter with the letter at the candidate. If they are equal, the entry copies the entry at the candidate. If they differ, the entry is the candidate length, and the candidate falls back through the table until the letters agree or the index goes below zero.
For ABCDABD the first three positions all fail at once, because B, C and D do not match the first letter A, so each gets 0. At position 4 the letter A does match the first letter, so the entry copies T[0] and becomes -1. At position 5 the letter B matches the letter at candidate 1, which is B, and the entry copies T[1], a 0. Position 6, the D, fails against the C that follows the candidate AB, so its entry is 2, the length of the live border.
The work is small. The table takes at most 2k - 2 passes for a word of length k, for the same reason as the search: the candidate only moves forward, and falls back no further than it has come. The page shows each position, the letters compared, the rule applied and the fall-back chain, so the table is no longer a mystery to be accepted on trust.
Two tables that are not the same
Many descriptions give the classical prefix function instead. For each prefix of the word it records the length of the longest proper prefix that is also a suffix. For ABCDABD it is 0 0 0 0 1 2 0, with no minus ones and no final entry. The two tables are not interchangeable at a glance, and mixing them up is a common slip: the shape differs, the indexing differs, and the search loops that read them differ too.
Both are right. A search that reads the classical function follows the failure links one comparison at a time, and a search that reads T takes the shortcut that was baked in. They find exactly the same matches, and this page runs both so the lists can be compared, with the one in use named on each step.
Why the text pointer never moves back
Follow the two indices through a run. The text index j and the word index k change in three ways. On equal characters both advance. On a mismatch the word index falls to T[k] and the text stays put. If it falls below zero, the text advances and the word restarts at zero.
The start of the candidate match is j minus k. Every pass either advances j or pushes that start to the right, and neither can happen more than n times for a text of length n. So the loop runs at most 2n times. Each pass compares exactly one pair of characters, so the loop count is the comparison count. On the example text of 23 characters the bound is 46, and the search needs 27 of 46 passes. It finds ABCDABD at 15.
Compare the cost with the naive search on the same input: 40 comparisons against 27. The gap grows with repetition. On the six-A word and the 30-A text the counts are 175 and 55, naive first: the KMP search needs 55 where the naive one needs 175. On real prose, where mismatches come early, the gap is small.
Overlapping matches and the entry after the last letter
What should the search do after it finds a complete match? Starting again at zero is the tempting answer, and it loses matches. Search for ABAB in ABABAB. The first match is at 0. The last two letters AB are also the start of another ABAB at 2. A search that resets to zero finds only 0.
This is what the last entry of the table is for. After a full match the word index goes to T of the word length, never to zero, and the overlapping match at 2 is found. The page has a switch for this. Turn it off and the search continues from the end of the match, which is a different task with a different answer.
A second slip is to restart the word from its first letter after a mismatch without re-reading the text letter that failed. Search for AAB in AAAB that way and nothing is found, though the word is at 1. The table does the right thing for you: the word index drops, and the failing letter is compared again.
Where it sits among the alternatives
Boyer-Moore is the benchmark for practical use. It compares from the end of the word and can skip sections of the text, so it is often faster on ordinary prose. Rabin-Karp hashes the word and slides a rolling hash along the text, checking only where the hashes agree. Aho-Corasick looks for a whole dictionary of words at once, and it is built on a structure that resembles the failure links here.
Knuth-Morris-Pratt earns its place by its guarantee. Preprocessing costs time in the length of the word and the search costs time in the length of the text, in the worst case and not only on average. It never needs to back up, so it can read a stream that cannot be rewound.
What the page does not do
It searches for one word in one text, with printable ASCII letters compared exactly. Unicode normalisation, several words at once, approximate matching and large text engines are left out, and so are the Boyer-Moore and Rabin-Karp methods, which are named and not run. The counts come from running the search itself, the naive count and the random self-test run in a background worker, and nothing you type leaves your device.
Sources
Every source consulted for this guide. Links checked November 12, 2026.
- Knuth-Morris-Pratt algorithm Wikipedia (CC BY-SA)
- String-searching algorithm Wikipedia (CC BY-SA)
- Boyer-Moore string-search algorithm Wikipedia (CC BY-SA)
- Rabin-Karp algorithm Wikipedia (CC BY-SA)
- Aho-Corasick algorithm Wikipedia (CC BY-SA)
- Deterministic finite automaton Wikipedia (CC BY-SA)
- Donald Knuth Wikipedia (CC BY-SA)
- Vaughan Pratt Wikipedia (CC BY-SA)
- James H. Morris Wikipedia (CC BY-SA)
- Web Workers API MDN Web Docs (CC BY-SA)