Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt algorithm (KMP algorithm) is a deterministic linear-time substring search method in computation and algorithms that locates all occurrences of a pattern string P of length m within a text string T of length n in O(n + m) worst-case time without ever backtracking the text pointer. Conceived in 1970 by Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt—and published jointly in the SIAM Journal on Computing in 1977—the algorithm preprocesses the pattern in Θ(m) time and space to construct an auxiliary prefix function (also called the failure function or longest proper border array), denoted π[1..m]. Whenever a character mismatch occurs after q matched symbols, π[q] tells the matcher the longest prefix of P that is simultaneously a proper suffix of the already-matched substring P[1..q], enabling the pattern to shift forward to the next viable alignment while preserving all information gained from previous character comparisons.

Prior to KMP, the standard brute-force sliding-window matcher tested each of the n − m + 1 candidate starting positions independently, resetting the text index backward after every mismatch and incurring Θ(nm) worst-case time on repetitive inputs such as searching for P = "AAAAB" inside T = "AAAAAAAAAAAAAAAAB". Inspired by Stephen Cook's 1970 theorem that any two-way deterministic pushdown automaton can be simulated on a random-access machine in linear time, Knuth and Pratt independently derived the general automaton simplification while Morris implemented the equivalent prefix-shift table inside a production text editor for the CDC 6400 operating system at the University of California, Berkeley.

Proper Borders of a Substring

Let Σ be a finite or countably infinite alphabet, let T[1..n] ∈ Σⁿ be the text string, and let P[1..m] ∈ Σ^m be the query pattern (with m ≤ n). For any integer q ∈ {1, 2, ..., m}, let P_q = P[1..q] denote the prefix of P of length q.

A substring w is called a border of P_q if w is both a prefix of P_q and a suffix of P_q. A border w is a proper border if 0 ≤ |w| < q (meaning w does not span the entire string P_q). Suppose that at a given stage of the search, the first q characters of the pattern match the text ending at text position i:

P[1..q] = T[i − q + 1 .. i]

while the next character mismatches (P[q + 1] ≠ T[i + 1], or q = m after a complete match). Any smaller shift of the pattern that aligns a shorter prefix P[1..k] (with 0 ≤ k < q) against the text suffix T[i − k + 1 .. i] can succeed only if P[1..k] equals the suffix of P[1..q] of length k—that is, only if P[1..k] is a proper border of P_q.

Definition of the Prefix Table π[q]

The KMP prefix function π : {1, 2, ..., m} → {0, 1, ..., m − 1} assigns to each prefix length q the length of the longest proper border of P_q:

π[q] = max { k : 0 ≤ k < q and P[1..k] is a suffix of P[1..q] }

By definition, π[1] = 0 because the only proper prefix of a single-character string is the empty string ε of length 0. Furthermore, iterating the prefix function generates every proper border of P_q in strictly decreasing order of length:

• Border sequence: π[q] > π[π[q]] > π⁽³⁾[q] > ··· > π^(r)[q] = 0

This border transitivity lemma holds because any proper border of length j < π[q] of P_q sits inside the suffix of P_q of length π[q], which is identical to P[1..π[q]]; hence j must also be a proper border of P_π[q].

Worked Example of π[q] on a Repetitive Genomic Motif

Consider the 10-nucleotide pattern P[1..10] = "ACACAGTACA" (m = 10). The table below lists each prefix P_q, its longest proper border, and the resulting shift value q − π[q]:

If a mismatch occurs at q = 5 (after matching "ACACA" against the text and failing on P[6] = 'G'), the algorithm looks up π[5] = 3, shifting the pattern forward by 5 − 3 = 2 positions so that P[1..3] = "ACA" remains aligned with the last three matched text symbols without re-reading them, and immediately tests P[4] = 'C' against the current text character T[i + 1].

Two-Phase Linear-Time Procedure

The Knuth-Morris-Pratt algorithm uses two nearly identical routines: Compute-Prefix-Function(P) (which matches P[2..m] against P[1..m − 1] using dynamic programming along the border chain) and KMP-Matcher(T, P) (which scans T[1..n]).

In Compute-Prefix-Function(P):

1. Initialize π[1] ← 0 and border length k ← 0.
2. For q = 2 to m:
   • While k > 0 and P[k + 1] ≠ P[q], fall back along the border chain: k ← π[k].
   • If P[k + 1] = P[q], increment the matched border length: k ← k + 1.
   • Record π[q] ← k.

In KMP-Matcher(T, P):

1. Compute π[1..m] and initialize matched prefix length q ← 0.
2. For text index i = 1 to n:
   • While q > 0 and P[q + 1] ≠ T[i], fall back: q ← π[q].
   • If P[q + 1] = T[i], advance the pattern state: q ← q + 1.
   • If q = m, report a full pattern occurrence at starting index i − m + 1 and set q ← π[m] to search for overlapping matches.

Amortized Potential Proof of Θ(n + m) Time

At first glance, the inner while loop (q ← π[q]) inside the outer for loop (i = 1 to n) might appear to require O(m) steps per text character, which would yield O(nm). However, an amortized potential argument (a cornerstone of computational complexity theory) proves that the inner loop executes at most n times in total across the entire scan of T:

• Define the non-negative potential function Φ(i) = q, the length of the currently matched pattern prefix after processing T[i], initialized at Φ(0) = 0.
• During iteration i of the outer for loop, the conditional match step (P[q + 1] = T[i]) can increment q by at most 1. Across all n iterations of the outer loop, q can therefore increase by at most n units in total.
• Conversely, every execution of the body of the inner while loop replaces q with π[q]. Because π[q] ≤ q − 1 for all q ≥ 1, each inner-loop iteration decreases Φ = q by at least 1.
• Because Φ starts at 0, never becomes negative (Φ(i) ≥ 0), and increases at most n times by 1, the inner while loop body can execute at most n times across the entire run.

Each character comparison P[q + 1] ≟ T[i] either succeeds (advancing i in the outer loop, at most n times) or fails (triggering a border fallback or leaving q = 0). More tightly, because the first text character T[1] cannot trigger a fallback, the total number of character comparisons during the text scan is bounded by 2n − 1 (and during preprocessing by 2m − 3).

Strong Prefix Table (π′) and Fibonacci String Delay Bound

In the basic prefix table π[q], a mismatch on P[q + 1] ≠ T[i] may shift the pattern to state k = π[q] where the next pattern character P[k + 1] is identical to the character P[q + 1] that just failed against T[i]. For example, in our table for "ACACAGTACA", at q = 4 (P[5] = 'A'), falling back to k = π[4] = 2 leads to P[3] = 'A', which is guaranteed to fail again against T[i].

Knuth, Morris, and Pratt eliminated these redundant comparisons by defining the strong failure table π′[q]:

• π′[q] = π[q] if P[π[q] + 1] ≠ P[q + 1]
• π′[q] = π′[π[q]] if P[π[q] + 1] = P[q + 1]

With π′[q], the worst-case number of consecutive fallback steps on a single text character T[i] occurs when P is a Fibonacci word (built by F_k = F_k−1F_k−2, such as "ABAABABAABAAB"), where the maximum delay on a single text symbol is bounded by 1 + log_φ m comparisons, where φ = (1 + √5) / 2 ≈ 1.618 is the golden ratio.

Because KMP never backtracks in the text stream T and requires only O(m) working memory independent of alphabet size |Σ|, it is the algorithm of choice when reading unbuffered network sockets, UNIX pipes, or magnetic tape streams, and when the alphabet |Σ| is small (such as binary bitstreams or the 4-letter DNA alphabet {A, C, G, T}) where right-to-left skipping algorithms gain fewer long shifts. In bioinformatics, KMP and its multi-pattern generalization—Alfred V. Aho and Margaret J. Corasick's 1975 Aho-Corasick trie automaton—are used for rapid scanning of restriction endonuclease cleavage sites, CRISPR protospacer adjacent motifs (PAMs), adapter trimming in raw sequencing reads, and seed filtering prior to banded sequence alignment.

Why does the Knuth-Morris-Pratt algorithm never move the text pointer backward?

At every step i, the matched prefix state q records that the last q characters read from the text (T[i − q + 1 .. i]) are identical to the pattern prefix P[1..q]. Because those q text characters are already known to equal P[1..q], any valid shift of the pattern within that window depends only on self-overlaps (proper borders) inside P[1..q], which are precomputed in π[q] before reading the text.

When is Boyer-Moore preferred over the Knuth-Morris-Pratt algorithm?

The Knuth-Morris-Pratt algorithm inspects every text character at least once, taking Θ(n) time in both the best and worst cases. When the text resides in random-access memory and the alphabet |Σ| is moderately large (such as ASCII text or 20-letter protein sequences) with pattern length m ≥ 5, the Boyer-Moore algorithm scans the pattern from right to left and skips across non-matching text segments in O(n / m) sublinear average time.

How does KMP relate to the Aho-Corasick multi-pattern algorithm?

The Aho-Corasick algorithm (1975) is the direct generalization of KMP from a single pattern string to a finite dictionary of k patterns {P₁, ..., P_k}. It organizes all patterns into a prefix tree (trie) and equips every trie node u with a KMP-style failure link pointing to the node representing the longest proper suffix of u's string that is also a prefix of some pattern in the dictionary.

1. Knuth, D. E., Morris, J. H., Jr., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323–350. https://doi.org/10.1137/0206024
2. Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: An aid to bibliographic search. Communications of the ACM, 18(6), 333–340. https://doi.org/10.1145/360825.360855
3. Cook, S. A. (1971). Linear time simulation of deterministic two-way pushdown automata. In Proceedings of the IFIP Congress 1971, Vol. 1 (pp. 75–80). North-Holland. https://doi.org/10.1145/800157.805047
4. Crochemore, M., & Rytter, W. (2002). Jewels of Stringology: Text Algorithms. World Scientific Publishing. https://doi.org/10.1142/4838