KMP string search

The problem it solves

Find every occurrence of a pattern in a text. The naive method — try each alignment, compare until mismatch — is fine on random text and catastrophic on repetitive text: searching for aaab in a text of ten thousand as compares almost four characters per alignment, O(n·m) in earnest. The waste has a specific shape: after matching aaa and failing on b, the naive method slides one position and re-reads characters it has already seen, learning nothing it did not already know.

Knuth–Morris–Pratt’s response is a precise accounting of that discarded knowledge. When a mismatch happens after j successful matches, those j characters are not random — they are, by definition, the first j characters of the pattern. Whatever re-alignment could possibly succeed next is determined by the pattern alone, and can therefore be computed before the search begins. The result is the failure table, and with it a guarantee with real teeth: the text pointer never moves backwards — every text character is read once, giving O(n + m) unconditionally, adversarial input included. Beyond searching, the failure function itself answers questions — shortest period of a string, shortest palindromic prefix — that make KMP a tool rather than just a search.

The intuition — and where it breaks down

Suppose you have matched ababa and the next text character breaks the match. The naive move surrenders all five characters. But look at what you hold: the text you just matched is ababa, and ababa ends with aba — which is also how the pattern begins. So a re-alignment three characters back is already three-fifths matched, guaranteed, sight unseen. No re-alignment between “here” and “three back” can work (any such overlap would itself be a prefix-suffix of ababa, and three is the longest). Slide the pattern, keep the text pointer planted, resume comparing.

The failure table is this reasoning done once per pattern position: fail[j] = the length of the longest proper prefix of pattern[0..j] that is also its suffix — how much of a j-length match survives the best possible slide. “Proper” excludes the whole string (a string trivially equals itself); that word carries real weight, and dropping it is a classic implementation bug. On mismatch after j matches: j = fail[j−1], repeat while mismatching, and never touch i.

Where the intuition breaks down: people expect the table to encode “where to restart in the text” — it does not, and cannot; it speaks only about the pattern’s self-overlap. The text is never consulted in building it, which is why the table can be built by running the matcher on the pattern against itself — a sentence that sounds circular and is actually the implementation. The player draws the table as the third row of the sheet so the mismatch-jump can be read directly off the drawing: the first prediction question asks for a fail[] entry, and computing one by hand — sliding the pattern against itself — is the moment the algorithm stops being magic.

Loading…

A walkthrough you can check

Search for ababc in abababc…. The failure table for ababc is [0, 0, 1, 2, 0].

1. Match a, b, a, b — four characters, i = 3, j = 4.
2. Text position 4 holds a; pattern[4] is c. Mismatch after 4 matches. Naive would slide one and re-read from text position 1. KMP consults fail[3] = 2: the matched abab ends with ab, which is also how the pattern begins. j falls to 2. i stays at 4.
3. Compare text[4] = a against pattern[2] = a — match, immediately. The two surviving characters were never re-verified; the table proved them.
4. Continue: b, then c — j reaches 5, occurrence reported at position 2.

Follow i through the whole run: 0, 1, 2, 3, 4, 4, 5, 6 — pauses, never retreats. The unit suite asserts this monotonicity on every trace, because it is not a stylistic nicety; it is the complexity proof, visible.

The invariant

At every moment, pattern[0..j−1] equals the last j characters of the text read so far — and i never decreases. The matching branch extends both sides by one character. The mismatch branch is where the induction earns its keep: replacing j by fail[j−1] shrinks the claim from “the last j characters match the prefix” to “the last fail[j−1] characters do” — true precisely because fail is a prefix-suffix overlap: the suffix half lives in the text, the prefix half is the new claim. Nothing about the text is re-examined, so i stands.

The table’s own invariant mirrors it: while building, fail[0..j−1] are final and k equals fail[j−1]’s candidate — the same fall-back logic, applied to the pattern against itself. This self-application is worth sitting with: the matcher and the table-builder are the same eight lines pointed at different strings, and understanding one is understanding both.

Complexity, derived

The subtle claim is that the inner while loop does not multiply. Amortise over j: each of the n outer iterations increases j by at most 1; the while loop strictly decreases j and j never goes negative. Total decrease ≤ total increase ≤ n, so all fall-backs across the whole run cost O(n) combined. Search: O(n). Table construction, by the identical argument on the pattern: O(m). Total O(n + m), space O(m) for the table — and no input, however adversarial, changes any of it. That unconditional guarantee is KMP’s actual product; on random text the naive algorithm is nearly linear too, and saying so is the honest framing interviewers respect.

The counters panel shows the amortisation empirically: comparisons land under 2n on every preset, including the self-overlapping one built to punish naive search.

What people get wrong

• Off-by-one on the fall-back: it is j = fail[j−1] — the table is consulted at the last matched position, not the mismatched one. The wrong index usually still passes small tests, which is what makes it vicious.
• Dropping “proper”: allowing the whole string as its own prefix-suffix makes fail[j] = j+1-ish nonsense and the matcher loops forever on some inputs.
• Missing overlapping occurrences: after a full match, j must fall back to fail[m−1], not to 0 — aaa occurs three times in aaaaa, and the repeat preset exists to catch the version that reports one.
• Moving i on mismatch: the moment the text pointer retreats, the algorithm is naive search with extra bookkeeping.
• Building the table with special-cased loops instead of recognising it as the matcher run on the pattern itself — correct is possible that way, but the elegance is the understanding.

Implementation notes

Two functions, sixteen lines total, and the displayed sources keep them line-matched. Build the table with the same fall-back loop as the search — reviewers should see the symmetry. Return all occurrences, falling back after each hit; returning just the first is a caller decision, not the algorithm’s.

The failure function’s side careers are worth knowing. Shortest period: m − fail[m−1] — if it divides m, the string is that period repeated (the Repeated Substring Pattern problem, solved in one line once the table exists). Shortest palindromic prefix (Shortest Palindrome): run the table on pattern + '#' + reversed(pattern). String automata: the table is the spine of the KMP automaton, and one construction step away from Aho–Corasick’s multi-pattern failure links — the trie essay picks up that thread.

Practical positioning: standard-library indexOf typically uses tuned variants (Boyer–Moore–Horspool, Two-Way) that are faster on average by skipping forward; KMP’s niche is the worst-case guarantee, streaming input (each text character processed once, no lookback — ideal when the text cannot be rewound), and the failure function itself. Say “for one-off searches, use the library” before the interviewer says it for you.

The follow-up questions

What exactly does fail[j] mean? The length of the longest proper prefix of pattern[0..j] that is also its suffix — equivalently, how many matched characters provably survive the best possible slide after a mismatch.

Why is it linear despite nested loops? Amortisation on j: it rises at most n times by one, and the inner loop only lowers it. Falls cannot exceed rises, so the loops sum to O(n) rather than multiplying.

How is the table built? By the matcher itself, run on the pattern against the pattern. Same fall-back logic, one pass, O(m) — the self-similarity is the whole construction.

When would you actually use it over the standard library? Streaming text you cannot rewind, adversarial or highly repetitive inputs where the worst case is live, and any problem whose real question is the failure function — periods, palindromic prefixes, automaton construction.