Knuth-Morris-Pratt
Knuth-Morris-Pratt builds a table over the pattern alone: for each position, the length of the longest proper prefix of the pattern that is also a suffix of the part up to that position. When a mismatch happens after j characters have agreed, that table says how much of those j characters is still usable, so the pattern slides forward by exactly the unusable part and the text pointer never moves back.
How far it jumps
Move by whatever the part that already matched tells you.
When it is the right choice
It is the right choice whenever the worst case matters — the running time is linear in the text length whatever the text is, which none of the naive or Boyer-Moore family can promise. It is also the natural choice when the text arrives as a stream, because the text pointer never goes backwards and so nothing has to be kept. What it is not is the fastest in practice on ordinary text: Boyer-Moore's skips are bigger when the alphabet is large, and Knuth-Morris-Pratt still touches every character at least once.
How it works
- Build the prefix table over the pattern by comparing the pattern against itself, one position at a time.
- When the next characters agree, the current border grows by one and that length is recorded.
- When they disagree, fall back to the border of the border and try again, until either something agrees or there is no border left.
- Search by comparing the text against the pattern from the left, advancing both on every agreement.
- On a mismatch, look up the border for the part that agreed and move the pattern forward by the rest; the text pointer stays exactly where it is.
- On a full match, record the occurrence and fall back by the border, so overlapping occurrences are still found.
Worth noticing
- The table is built by matching the pattern against itself. That is the step most explanations skip, and it is why this page steps through it rather than handing the numbers over.
- The text pointer never decreases during the search. Scrub back and forth and watch it: everything the algorithm saves comes from that one property.
- On the repeated-characters scenario the table is not the interesting number — the comparisons counter is. Race this against naive search on the same text.
Cost
- Best
- O(n + m)
- Average
- O(n + m)
- Worst
- O(n + m)
- Extra space
- O(m)
- Longest text
- 160 characters
- Longest pattern
- 24 characters
The limits are pedagogical rather than technical: one column is drawn per character, and a run has to stay short enough to sit and watch. A text and pattern that would take more than three thousand steps on this algorithm are refused before a single step is generated — and because that depends on the text itself and not only on its length, the tool counts the steps first rather than guessing from a formula.