The waste the naive scan refuses to learn from
The previous guide framed the problem and timed the obvious method: slide a pattern P of length m along a text T of length n, and at each of the roughly n starting positions compare character by character. When characters keep matching but then one fails, the naive scan shrugs, shifts the pattern one step right, and starts comparing again from the very first character of P. That is naive matching, and its worst case is O(n*m) — pattern `aaaa...ab` against text `aaaa...aa` makes nearly every window do almost m comparisons before failing.
Look closely at what gets thrown away. Suppose P = `abcab` and we have already matched `abca` inside the text before the fifth character disagrees. The naive scan now nudges P right by one and re-examines those text characters from scratch. But we already know what they were — they spelled `abca`, because they matched the pattern. The text positions we are about to re-read are not a mystery; they are a known prefix of P. Re-reading them is the waste, and it is avoidable precisely because the information lives inside the pattern, which we can study before the search even begins.
So the whole idea of Knuth-Morris-Pratt is a trade. Spend a little time up front analysing P alone — independent of any text — to build a table that answers one question: after a mismatch, how far can the pattern safely jump so that no already-matched text ever has to be read again? With that table in hand, the text pointer marches strictly forward and the search becomes exact matching in O(n + m) time. The art is entirely in defining and computing the table.
Borders: the prefix function, defined carefully
The table is built from one idea: a border. A border of a string is a proper prefix that is also a suffix — "proper" meaning shorter than the whole string. In `abcab` the prefix `ab` equals the suffix `ab`, so `ab` is a border of length 2. The empty string is a border of everything (length 0). The prefix function, written pi, records for each prefix of P the length of its longest border: pi[i] is the length of the longest border of P[0..i], the prefix ending at position i.
Why borders? Because a border is exactly a place the pattern can resume after a mismatch without losing ground. Suppose we matched a prefix of P of length L against the text and then character L+1 failed. The last L text characters spell P[0..L-1]. If P has a border of length b, then the first b characters of P equal the last b of that matched stretch — so those b text characters are already matched against the start of P. We may slide P forward so its length-b prefix lines up there, and continue comparing from P's character b. The longest border gives the smallest safe shift; jumping further could skip a genuine occurrence.
P = a b a b a b c a idx 0 1 2 3 4 5 6 7 pi 0 0 1 2 3 4 0 1 # pi[4]=3: prefix "ababa" has longest border "aba" (len 3) # pi[6]=0: prefix "abababc" has no nonempty border
Computing pi in linear time — the table builds itself
The beautiful part is that the prefix function is computed by running KMP on the pattern against itself. We build pi left to right. Keep a length `k` = the longest border of the prefix just before the current character. To extend to the next character P[i], we ask: does P[k] equal P[i]? If yes, the border grows by one, so pi[i] = k + 1. If no, we must shorten our candidate border — and the shorter candidate to try is itself a border of a border, which we have already recorded as pi[k-1]. We keep falling back via k = pi[k-1] until either the characters match or k reaches 0.
- Set pi[0] = 0 (a one-character prefix has only the empty border) and k = 0. Walk i from 1 to m-1.
- While k > 0 and P[k] != P[i], fall back: k = pi[k-1]. This tries the next-longest border as the new candidate, never re-scanning from zero.
- If now P[k] == P[i], the border extends: increment k. Either way, record pi[i] = k and move to the next i.
Why is this linear and not quadratic, given the inner fallback loop? Use amortized reasoning. The variable k rises by at most 1 on each of the m iterations, so it increases by at most m in total across the whole run. Each fallback step strictly decreases k by at least 1. Since k starts at 0, stays non-negative, and only ever rose by m in total, the total number of fallback decreases over the entire computation is also at most m. The loop body therefore runs O(m) times in aggregate even though a single iteration may fall back many times. That is the aggregate method doing exactly its job.
Running the search: the text pointer never backs up
With pi in hand, the search is the same loop, now reading text. Keep a position `q` = number of pattern characters currently matched. Scan the text left to right with index i. On each text character T[i]: while q > 0 and P[q] != T[i], fall back q = pi[q-1] (reuse the border!). If P[q] == T[i], increment q. If q reaches m, we have found a full occurrence ending at i; record it and fall back q = pi[m-1] to keep searching for overlapping matches. The text index i only ever moves forward — that is the whole point.
Trace a tiny case. P = `aba`, so pi = [0,0,1]. Text T = `ababa`. At i=0,1,2 we match `aba`: q hits 3, report a match ending at index 2, then fall back to q = pi[2] = 1 (the border `a` is still matched). At i=3, T[3]=`b` and P[1]=`b` match, q=2. At i=4, T[4]=`a` and P[2]=`a` match, q=3, report a second match ending at index 4. Two occurrences, overlapping, found in one forward sweep of five characters — the text pointer never rewound, and the overlap was caught precisely because we resumed from the border rather than from scratch.
The same amortized argument bounds the search. The text index i advances exactly n times. q rises by at most 1 per advance, hence by at most n in total, and each fallback drops it by at least 1, so total fallbacks are at most n. Search is therefore O(n), and with the O(m) preprocessing the whole of KMP is O(n + m) — linear in the combined input size, with no hidden dependence on the alphabet. This is the same forward-only, never-re-read discipline the Z-algorithm in the next guide reaches by a different route.
Why it is correct, and what to keep honest about
Correctness rests on a clean loop invariant for the search: after processing T[0..i], q equals the length of the longest prefix of P that is also a suffix of T[0..i]. Read that twice — it says q is the longest pattern-prefix we could possibly still be in the middle of, given everything seen so far. When q reaches m, that longest prefix is all of P, so P really does end at i: a genuine occurrence, not a false alarm. The fallback step is precisely what re-establishes the invariant after a mismatch, because the next viable prefix-suffix is the next-longest border, which pi[q-1] hands us directly.
That the invariant survives every step is itself a proof by induction on i, leaning on a small fact about borders: every border of a string, other than the longest, is a border of its longest border. That fact is exactly why the fallback chain q, pi[q-1], pi[pi[q-1]-1], ... enumerates all candidate prefix-lengths in decreasing order without skipping one — so the loop always finds the true longest match and never overshoots a valid occurrence.
Two honest limits. First, KMP solves exact single-pattern matching over a sequence read left to right; it does not by itself give approximate matching, nor multiple patterns at once — that is where Aho-Corasick later generalizes the same border idea to many patterns. Second, KMP's win is comparisons saved, not a magic speedup of I/O: the constant factor is small and predictable, but if your real cost is reading bytes from disk, any linear scanner, including Rabin-Karp, pays the same I/O. KMP's distinctive promise is the guaranteed linear comparison count with zero text re-reading, derived entirely from analysing the pattern before the text is ever touched.