To find a pattern in a text, the obvious method lines the pattern up at each position and compares character by character. After a mismatch it slides the pattern one step and starts comparing from scratch, re-reading text it has already seen. With a text of n characters and a pattern of m, that can take about n · m comparisons.
When a mismatch comes after j matching characters, we know exactly what those j text characters were: the first j characters of the pattern. So it's possible to work out in advance how far the pattern can slide without missing a match, using only the pattern itself.
A border of a string is a proper prefix that is also a suffix: "ABA" is a border of "ABABA". The prefix table π stores, for each position i of the pattern, the length of the longest border of pattern[0..i]. After a mismatch with j characters matched, the last π[j − 1] text characters still match the start of the pattern, so the scan continues with j = π[j − 1]. The text index never moves backwards.
π is built with the same trick, matching the pattern against itself. Keep k, the length of the current border. To extend it with the next character, compare it with pattern[k]: if they match, the border grows by one. If not, fall back to the next shorter border, k = π[k − 1], and try again; when k reaches 0 with no match, π is 0.
The yellow cells are being compared; the green ones match so far. While matching, the pattern row (and its π values) slides along under the text. The footer counts character comparisons.
| Naive | KMP | |
|---|---|---|
| Preparation | None | O(m) to build π |
| Matching | O(n · m) in the worst case | O(n): at most 2n comparisons |
| Reads the text | Back and forth | Left to right, once |