Knuth-Morris-Pratt String Matching
Imagine searching a two-gigabyte log file for a suspicious command string. Or scanning a genome of three billion bases for a short genetic marker. The naive approach re-checks the pattern from scratch at every position in the text. On adversarial inputs — like searching for `AAAAAB` inside a text of all `A`s — this degrades to quadratic time. That quadratic blow-up is not a theoretical curiosity. It is a real denial-of-service vector against any system that matches user-supplied patterns naively. The Knuth-Morris-Pratt (KMP) algorithm fixes this permanently. It preprocesses the pattern once, in linear time. This builds a small table. The table records how much matching work can be reused after a mismatch. Armed with this table, KMP scans the text exactly once, left to right. It never re-reads a character it has already looked at. The total work is bounded by `O(n + m)`. Here `n` is the text length and `m` is the pattern length. This is a hard worst-case guarantee, not just an average-case improvement. The deep idea that makes this possible is shared by nearly every other efficient string algorithm. That idea is the structure of borders (a string's own prefixes that are also suffixes of some prefix). When a match fails partway through the pattern, the characters already matched are not thrown away. They encode information about themselves. This tells us exactly how far we can safely slide the pattern forward. It also tells us exactly which prefix of the pattern is already known to match the new alignment. This article builds the failure table (the prefix function) from first principles. It proves its two amortized-linear-time guarantees. It walks a full non-trivial trace. Finally, it connects the technique to the machinery — suffix automata, suffix trees, and suffix arrays. That machinery generalizes matching to multiple patterns and full-text indexing.
- KMP matches a pattern of length `m` in a text of length `n` in worst-case `O(n + m)` time, with `O(m)` extra space.
- The core object is the prefix function `π`, where `π[i]` is the length of the longest proper prefix of `pattern[0..i]` that is also a suffix of it (a border).
- On a mismatch, KMP never backtracks the text pointer; it uses `π` to jump the pattern pointer to the next-best partial match.
- Building `π` itself uses the KMP idea recursively — matching the pattern against itself — also in `O(m)` time.
- Correctness rests on an invariant: at every step, the matched prefix of the pattern is the longest prefix of the pattern that matches ending at the current text position.
- KMP generalizes to real-time streaming search and is a stepping stone toward Suffix Trees and Suffix Arrays for full-text indexing.
Precomputing the pattern's own self-overlaps (its longest borders) lets the search phase discard mismatched information without ever re-scanning the text — turning matching into a true two-pointer linear scan.
The idea
Given a text `T` of length `n` and a pattern `P` of length `m`, the string matching problem asks for all starting positions `s` such that `T[s .. s+m-1] = P`. Naive String Matching and the Matching Problem solves this by trying every alignment `s` from `0` to `n-m`, and for each one comparing characters left to right until a mismatch or a full match. Its worst case is `O(nm)`: a text of `n` copies of `A` and a pattern `AAAA...AB` forces almost `m` comparisons at every one of the `~n` alignments. The wasted work in the naive method comes from throwing away all the information gained during a partial match. Suppose the pattern has matched the text for `q` characters and then mismatches at the `(q+1)`-th character. The naive algorithm slides the pattern one position to the right and starts comparing from scratch — but the substring `T[s+1 .. s+q-1]` is a suffix of the prefix `P[0..q-1]` that we already know matched. If a prefix of `P` happens to equal a suffix of `P[0..q-1]`, that overlap is already verified in the text, and we can skip re-checking it. This motivates the central definition. For a string `P` of length `m`, define the prefix function `π : {0, ..., m-1} → {0, ..., m-1}` by ``` π[i] = length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i] ``` A proper prefix/suffix pair of a string that is equal is called a border of that string (some texts call it a "failure link"). So `π[i]` is the length of the longest border of `P[0..i]`. When a mismatch occurs after matching `q` characters of the pattern, `π[q-1]` tells us exactly how many characters of the pattern are still guaranteed to match — we can resume comparison at pattern position `π[q-1]` without moving the text pointer backward at all. This is the entire algorithm: build `π` once in `O(m)`, then scan `T` once in `O(n)` using `π` to recover from every mismatch.
How it works
KMP has two phases that share the same underlying technique.
Phase 1 — build the prefix function. We compute `π[0..m-1]` by matching the pattern against itself. Conceptually we ask, for each prefix `P[0..i]`, "what is its longest border?" We compute this incrementally: `π[i]` is derived from `π[i-1]` by trying to extend the previous border by one character; if the next characters disagree, we fall back to the border of the border (following `π` backward, exactly the recursive self-similarity that also drives the search phase).
Phase 2 — scan the text. Maintain an index `i` into `T` and an index `q` counting how many pattern characters currently match ending at `T[i]`. Advance `i` through the text once. When `T[i] = P[q]`, increment `q`. When they disagree (and `q > 0`), fall back via `π[q-1]` — never moving `i` backward — and retry. When `q` reaches `m`, report a match at position `i - m + 1`, then fall back via `π[m-1]` to continue searching for overlapping occurrences. ``` function computePrefixFunction(P[0..m-1]): π[0] = 0 k = 0 # length of current matching border for i = 1 to m-1: while k > 0 and P[i] != P[k]: k = π[k-1] # fall back to border of the border if P[i] == P[k]: k = k + 1 π[i] = k return π function KMPSearch(T[0..n-1], P[0..m-1]): if m == 0: return all positions 0..n # edge case: empty pattern π = computePrefixFunction(P) q = 0 # number of pattern chars matched so far matches = [] for i = 0 to n-1: while q > 0 and T[i] != P[q]: q = π[q-1] # reuse: slide pattern using border info if T[i] == P[q]: q = q + 1 if q == m: matches.append(i - m + 1) q = π[q-1] # continue searching for overlaps return matches ``` Two details matter for correctness on edge cases. First, `π[0] = 0` always, since a single character has no proper nonempty prefix. Second, when `q` reaches `m` after a match, falling back to `π[m-1]` (rather than resetting `q` to `0`) correctly detects overlapping matches, such as `P = "AA"` inside `T = "AAAA"`.
Complexity & correctness
Time complexity — building `π`. The inner `while` loop decreases `k` and the outer `for` loop increases `k` by at most 1 per iteration. Since `k` starts at 0, stays non-negative, and is incremented at most `m-1` times total across the whole run, it can be decremented at most `m-1` times total. So the `while` loop body across the entire run of `computePrefixFunction` executes `O(m)` times, not `O(m)` per outer iteration. This is a standard amortized analysis via a potential function `Φ = k`: each outer iteration does `O(1)` work plus work proportional to the decrease in `Φ`, and `Φ` can decrease by at most as much as it has ever increased. Total: `O(m)`.
Time complexity — scanning `T`. Identical argument with `q` playing the role of `k`: `i` advances `n` times, `q` increases by at most 1 per step of `i`, so `q`'s total increase over the run is at most `n`, bounding the total number of `while`-loop fallback steps by `O(n)` as well. Overall search is `O(n)`. Combined with preprocessing, total time is ``` O(n + m) ``` which is optimal: any correct algorithm must read every character of the pattern and (in the worst case) every character of the text at least once.
Space complexity. The prefix function table needs `O(m)` integers; the search phase uses `O(1)` additional pointers. Total auxiliary space is `O(m)`, independent of `n` — important when `n` is a streamed input that need not be stored.
Correctness — the invariant. The key invariant maintained throughout `KMPSearch` is: > After processing `T[i]`, the value `q` equals the length of the longest prefix of `P` that is a suffix of `T[0..i]`. Base case: before any characters are read, `q = 0`, the longest prefix of `P` that is a suffix of the empty string is the empty prefix, length 0. Inductive step: suppose the invariant holds after `T[i-1]`, i.e., `q` is the longest such prefix length for `T[0..i-1]`. When we examine `T[i]`:
- If `P[q] = T[i]`, then extending the matched prefix by one character is valid, and this extended prefix (length `q+1`) is still the longest one — because any longer prefix of `P` matching a suffix of `T[0..i]` would have its own length-`q` prefix matching a suffix of `T[0..i-1]` that is at least as long as `q`, contradicting maximality of `q` at step `i-1` unless it equals `q`. So `q+1` is correct.
- If `P[q] \ne T[i]`, no extension of the current border works. We must find the longest prefix of `P` shorter than `q` that is also a border of `P[0..q-1]` (since it must simultaneously be a suffix of `T[0..i-1]`, which by induction is characterized by borders of `P[0..q-1]`), and check whether extending that by `T[i]` works. This is exactly `π[q-1]`, and possibly its own chain of fallbacks via `π`, — precisely what the `while` loop computes. The loop tries strictly decreasing candidate lengths in the correct order (longest border first), so it finds the true longest valid `q` before advancing `i`.
This proves that whenever `q` reaches `m`, we have found a suffix of `T[0..i]` equal to the entire pattern `P` — a genuine match ending at position `i`, with start `i - m + 1`. Conversely, the invariant guarantees no match is skipped: since `q` is tracked as the longest matching prefix at every position, no shorter, later-verifiable match ending earlier is ever missed by the fallback logic; all fallback values are borders of already-verified matched text, so they never assert a false match.
Tradeoffs. KMP guarantees worst-case linear time, unlike naive matching, but it is not always fastest in practice: the Boyer-Moore family often skips more characters on average using a bad-character heuristic, especially for large alphabets like ASCII/Unicode text. KMP shines when the alphabet is small (DNA, binary data) or when worst-case guarantees matter (security-sensitive matching, real-time systems, streaming data where you cannot re-read prior input — a property naive and even Boyer-Moore variants can violate, but which KMP's non-backtracking text pointer satisfies exactly).
Worked example
Let `T = "ABABABCABABABCABAB"` (length 19) and `P = "ABABCAB"` (length 7). Note this pattern has internal self-overlap, which is exactly the case that makes naive matching slow and demonstrates KMP's reuse of information.
Step 1: build `π` for `P = A B A B C A B`.
| i | P[i] | k before | comparison | k after | π[i] |
|---|---|---|---|---|---|
| 0 | A | 0 | (base case) | 0 | 0 |
| 1 | B | 0 | P[1]=B vs P[0]=A → mismatch | 0 | 0 |
| 2 | A | 0 | P[2]=A vs P[0]=A → match | 1 | 1 |
| 3 | B | 1 | P[3]=B vs P[1]=B → match | 2 | 2 |
| 4 | C | 2 | P[4]=C vs P[2]=A → mismatch, fallback k=π[1]=0; P[4]=C vs P[0]=A → mismatch | 0 | 0 |
| 5 | A | 0 | P[5]=A vs P[0]=A → match | 1 | 1 |
| 6 | B | 1 | P[6]=B vs P[1]=B → match | 2 | 2 |
So `π = [0, 0, 1, 2, 0, 1, 2]`.
Step 2: scan `T` with `q` starting at 0.
| i | T[i] | action | q after | |
|---|---|---|---|---|
| 0 | A | match P[0]=A | 1 | |
| 1 | B | match P[1]=B | 2 | |
| 2 | A | match P[2]=A | 3 | |
| 3 | B | match P[3]=B | 4 | |
| 4 | A | mismatch P[4]=C vs A; fallback q=π[3]=2; P[2]=A vs A → match | 3 | |
| 5 | B | match P[3]=B | 4 | |
| 6 | C | match P[4]=C | 5 | |
| 7 | A | match P[5]=A | 6 | |
| 8 | B | match P[6]=B | 7 = m → MATCH at i-m+1 = 8-7+1 = 2; fallback q=π[6]=2 | 2 |
| 9 | A | match P[2]=A | 3 | |
| 10 | B | match P[3]=B | 4 | |
| 11 | A | mismatch P[4]=C vs A; fallback q=π[3]=2; match | 3 | |
| 12 | B | match | 4 | |
| 13 | C | match P[4]=C | 5 | |
| 14 | A | match P[5]=A | 6 | |
| 15 | B | match P[6]=B | 7 → MATCH at 15-7+1 = 9; fallback q=π[6]=2 | 2 |
| 16 | A | match P[2]=A | 3 | |
| 17 | B | match P[3]=B | 4 | |
| 18 | (end) | — | — |
The algorithm reports matches starting at text positions 2 and 9 — verify: `T[2..8] = "ABABCAB"` ✓ and `T[9..15] = "ABABCAB"` ✓. Total character comparisons across the scan: 19 (`i` steps) plus 2 fallback re-comparisons at `i=4` and `i=11` = 21 comparisons for `n=19, m=7` — well within the `O(n+m)` bound, and crucially, `i` never moved backward.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Off-by-one in `π[i]` recursion | Forgetting `π[0] = 0` or indexing `P[k]` instead of `P[i]` in the comparison | Carefully separate "index into pattern being matched" (`i`) from "candidate border length" (`k`) |
| Forgetting to fall back after a full match | Only resetting `q = 0` after a match, missing overlapping occurrences | Use `q = π[m-1]` after reporting a match, not `q = 0` |
| Treating `π` as a "shift amount" like Boyer-Moore's tables | Confusing KMP's border-length semantics with bad-character/good-suffix shift tables | Remember `π[i]` is a length, and the resulting shift is `(i+1) - π[i]`, not `π[i]` itself |
| Rebuilding `π` per query on a fixed pattern | Not caching the prefix table when searching many texts with the same pattern | Precompute `π` once and reuse across all searches |
| Off-by-one at empty pattern or `m > n` | Special cases skipped, causing index-out-of-bounds | Explicitly handle `m == 0` (matches everywhere) and short-circuit when `m > n` |
| Assuming average case matches worst case | Believing naive matching is "usually fine" so KMP is unnecessary | Recognize adversarial or periodic inputs (e.g. `AAAA...A`) make naive matching quadratic in practice, not just theory |
Pioneers & history
The algorithm is named for Donald Knuth, Vaughan Pratt, and James H. Morris, who developed the linear-time technique in the early 1970s; independently, Yuri Matiyasevich had described a related automaton-based idea using a similar failure-function concept, and Morris later proved the connection to Knuth's work while both were investigating string-matching lower bounds. Knuth is broadly known across Algorithm Design Paradigms for foundational analyses of algorithmic efficiency, including the amortized-analysis style argument (the potential-function bound on the `while` loop) that certifies KMP's linear time.
Origins · 1 minDonald Ervin Knuth and how this was discovered
Knuth co-developed the KMP algorithm while studying lower bounds for string-matching complexity, and formalized the amortized-analysis argument that certifies its linear running time — a proof technique that became a staple of algorithm analysis far beyond string matching.
Where this matters
Text editors and command-line tools such as `grep` variants use failure-function-style matching (or hybrids with Boyer-Moore) to guarantee responsive search even on pathological input. Network intrusion detection systems (e.g., matching packet payloads against known attack signatures) rely on KMP-style automatons — often generalized to Aho-Corasick for many patterns simultaneously — precisely because an attacker who controls the input text must not be able to force quadratic-time behavior; this is a genuine security requirement, not just a performance nicety. Bioinformatics pipelines use KMP and its descendants to locate short genetic markers or primers within genomic sequences where the alphabet is small (`{A,C,G,T}`), a setting where KMP's small-alphabet efficiency is especially strong. Compilers and interpreters use related prefix-function ideas in lexical analysis and in implementing efficient substring search library functions. Finally, KMP's failure-function machinery is the conceptual seed for richer structures — the Aho-Corasick trie-automaton for multiple patterns, and ultimately Suffix Trees and Suffix Arrays, which index an entire text so that arbitrary pattern queries run in time proportional to the pattern length alone, independent of the text. The border concept also connects to ideas used in Edit Distance computations, where prefix/suffix overlap structure similarly helps prune redundant comparisons.
:::quiz[What does π[i] represent in the KMP prefix function?]
- The number of times character P[i] appears in the pattern
- The length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i] ✓
- The position in the text where the next mismatch will occur
- The total number of borders of the entire pattern
:::quiz[After reporting a match at position i-m+1, why does KMP set q = π[m-1] instead of q = 0?]
- To avoid an off-by-one error in the output index
- To correctly continue searching for possible overlapping matches ✓
- Because π[m-1] is always equal to 0 for any pattern
- To save memory by reusing the same variable
Ask the tutor: How does the prefix-function idea extend into the Aho-Corasick automaton for matching many patterns at once?
Why can't the text pointer i ever move backward in KMP?
This is the defining feature that gives KMP its linear-time guarantee and its suitability for streaming input. The invariant tracked by `q` already encodes everything relevant about `T[0..i-1]` — specifically, the longest prefix of `P` matching a suffix of the text seen so far. When a mismatch occurs, all the information needed to recover (the next-best candidate match length) is derivable purely from the pattern's own structure via `π`, without re-examining any text character. This means KMP can process a text stream character by character, discarding each character after processing it, using only `O(m)` memory — impossible for naive matching or algorithms that require backward re-scanning of the text.
How is the prefix function different from a suffix array or suffix tree?
The prefix function `π` is specific to one fixed pattern and only encodes self-overlap information about that pattern's own prefixes. A Suffix Trees and Suffix Arrays structure indexes an entire text (or corpus) so that any pattern can be searched afterward in time proportional to the pattern's length, independent of the text. KMP preprocesses the query (the pattern); suffix trees preprocess the data (the text). They solve related but distinct problems: KMP is optimal when you have one pattern and possibly many texts (or a data stream), while suffix trees/arrays are optimal when you have one large fixed text and many different pattern queries.
Does KMP handle multiple pattern occurrences, including overlapping ones?
Yes. After a full match is detected (`q` reaches `m`), the algorithm does not reset `q` to zero; instead it falls back to `q = π[m-1]`, the length of the longest proper border of the whole pattern. This correctly resumes the search using any self-overlap the pattern has with itself, so overlapping occurrences — such as `"AA"` occurring at positions 0 and 1 within `"AAA"` — are all reported. If the fallback were incorrectly set to zero, such overlapping matches would be silently missed.
Is KMP always faster than naive string matching in practice?
Not necessarily in the average case. On typical, non-adversarial text with a reasonably sized alphabet, naive matching's average-case behavior is close to linear because mismatches tend to occur quickly (within the first character or two), and Boyer-Moore-style algorithms often skip more text via bad-character heuristics, yielding sub-linear average behavior. KMP's real advantage is its worst-case guarantee: no input, however adversarially constructed, can force it beyond `O(n+m)`. This matters most in security-sensitive or real-time contexts where predictable performance is more valuable than average-case speed.
What happens if the pattern has no repeated substructure at all, like "ABCDE"?
Then every value of `π[i]` is 0, since no proper prefix of any prefix of the pattern repeats as a suffix. In this case, every mismatch causes KMP to fall back directly to `q = 0`, behaving very similarly to naive matching for that particular pattern — but still correctly, and still in linear time, because the text pointer still never moves backward. The prefix-function machinery costs nothing extra here; it simply confirms there is no reusable overlap to exploit, which is itself useful information the algorithm discovers automatically.
Can KMP be adapted to search for multiple patterns simultaneously?
Not directly with a single prefix function, since `π` is built for one specific pattern. However, the same failure-link idea generalizes: building a trie of multiple patterns and augmenting it with failure links (analogous to `π`, but pointing between trie nodes rather than within one linear string) yields the Aho-Corasick automaton, which matches an entire dictionary of patterns against a text in `O(n + sum of pattern lengths + number of matches)` time. This is the natural multi-pattern extension of the KMP idea and is widely used in intrusion detection and multi-keyword text scanning.
Why does the invariant proof require that q is the LONGEST matching prefix, not just any matching prefix?
If `q` were merely a valid matching length rather than the longest, the algorithm could report false negatives: it might advance `i` believing no match is forming when in fact a longer, still-valid partial match exists that was discarded. Longest-prefix tracking guarantees that whenever `q` reaches `m`, this is a genuine, complete, verifiable match, and also guarantees that the fallback chain via `π` explores candidates in the correct order (longest first) so no valid continuation is skipped. This maximality property is exactly what the inductive proof step establishes at each character.