vault

Knuth-Morris-Pratt

15 min read

Knuth-Morris-Pratt

Knuth-Morris-Pratt (KMP) finds every occurrence of a pattern P of length m inside a text T of length n in O(n + m) time — provably linear and, crucially, without ever moving backwards in T. The trick is a one-time preprocessing of P to build a failure function (also called the LPS array, “longest proper prefix that is also a suffix”). When a mismatch occurs after q matched characters, the failure function tells us the longest prefix of P that we already know matches the corresponding suffix of T — so we can resume from there instead of restarting. KMP was the first published algorithm to achieve linear-time pattern matching (Knuth, Morris & Pratt 1977) and remains the standard reference for amortized-analysis interview questions.

1. Intuition — What Would You Remember From a Mismatch?

Imagine you’re searching for the pattern ABABC inside the text ABABABC. You line them up and start comparing:

T: A B A B A B C
P: A B A B C
   ↑ ↑ ↑ ↑ ✗

You match ABAB and then mismatch (A in text, C in pattern). The naive approach throws away everything you just learned: shift the pattern by one position and restart from the beginning of P. That’s where the O(n·m) cost comes from — every mismatch sends you back to position 0 of the pattern, and each text character can be reread m times.

But you already know something useful. The text up to the mismatch was ABAB. That’s the same as the prefix ABAB of the pattern (because we matched it!). If we could spot that the prefix AB of the pattern is also a suffix of the matched portion ABAB, we’d realize: “shifting the pattern by 2 lines AB up against the AB at the end of what we already matched — no need to recheck those characters.” Slide the pattern by 2 and resume from position 2 of P instead of position 0.

T: A B A B A B C
P:     A B A B C
       (already match A B; resume at position 2 of P)
              ↑
              compare P[2]=A vs T[4]=A → match
                P[3]=B vs T[5]=B → match
                  P[4]=C vs T[6]=C → match → FOUND

The failure function is just a precomputed table that, for each position q in the pattern, stores “if you mismatch after matching q characters, what’s the longest prefix of P you can resume from without re-examining the text?” That length is exactly the length of the longest proper prefix of P[0..q-1] that is also a suffix of P[0..q-1] — hence the name LPS (Longest Proper Prefix that is also a Suffix). “Proper” means strictly shorter than the string itself; otherwise P[0..q-1] is trivially its own prefix and suffix and we’d just stay put.

The real-world analogy Knuth’s lectures use: when you’re trying to memorize a long phone number and slip up halfway through, you don’t start over from the area code — you back up to the most recent chunk that still matches what’s in your head. The failure function is your “how far back must I jump?” table, computed once for the phrase you’re trying to recognize.

2. Tiny Worked Example — Building the Failure Function

Let’s compute the failure function for P = "ABABCABAB" (length 9). I’ll write f[i] for the LPS value at position i, defined as the length of the longest proper prefix of P[0..i] (the prefix of length i+1) that is also a suffix of P[0..i]. Some references 1-index this and some store an extra sentinel; we use 0-indexed f[0..m-1].

iP[0..i]Proper prefixesProper suffixesLongest matchf[i]
0A(none)(none)—0
1ABAB—0
2ABAA, ABA, BAA1
3ABABA, AB, ABAB, AB, BABAB2
4ABABCA, AB, ABA, ABABC, BC, ABC, BABC—0
5ABABCA……A1
6ABABCAB……AB2
7ABABCABA……ABA3
8ABABCABAB……ABAB4

Read row 8: the prefix ABAB of length 4 equals the suffix ABAB of ABABCABAB. That’s the longest such proper match. The full string ABABCABAB matches itself trivially but is not “proper”.

Notice the structural pattern: f goes 0, 0, 1, 2, 0, 1, 2, 3, 4. After every mismatch jump (the 0 at i=4 — the C broke the run), the function climbs again as the suffix ABAB slowly rebuilds. The “climbing-then-falling” zigzag is characteristic of the failure function on patterns with repetitive structure, and the next section turns that intuition into an O(m) algorithm.

2.1 The Search Trace

Now use this f to find P = "ABABCABAB" inside T = "ABABDABACDABABCABAB" (length 19).

We maintain two indices: i walks forward through the text (never goes back), and q is “how many characters of P we’ve matched so far” (it goes back via f).

stepiT[i]qP[q]Action
10A0Amatch → q=1, i=1
21B1Bmatch → q=2, i=2
32A2Amatch → q=3, i=3
43B3Bmatch → q=4, i=4
54D4Cmismatch! q ← f[q-1] = f[3] = 2
64D2Amismatch (still). q ← f[1] = 0
74D0Amismatch, q == 0 → i=5
85A0Amatch → q=1, i=6
96B1Bmatch → q=2, i=7
107A2Amatch → q=3, i=8
118C3Bmismatch! q ← f[2] = 1
128C1Bmismatch! q ← f[0] = 0
138C0Amismatch, q == 0 → i=9
……………(continues until q reaches m=9 → match found)

Crucially, in the entire trace, i only ever moves forward. The text is read once; only the pattern pointer q ever reverses. That is the entire reason KMP works on streaming inputs (e.g., a network socket where you can’t seek backwards).

3. Pseudocode

3.1 Failure function

ComputeFailureFunction(P):
    m := length(P)
    f := array of size m, initialized to 0
    k := 0                        # length of the previous longest prefix-suffix
    for q in 1 .. m-1:
        # roll k back along earlier failure links until we either match
        # the next character or exhaust the chain back to 0
        while k > 0 and P[k] != P[q]:
            k := f[k - 1]
        if P[k] == P[q]:
            k := k + 1
        f[q] := k
    return f

KMP(T, P):
    n := length(T); m := length(P)
    if m == 0: return [0]
    f := ComputeFailureFunction(P)
    matches := empty list
    q := 0                         # number of characters of P matched so far
    for i in 0 .. n-1:
        while q > 0 and P[q] != T[i]:
            q := f[q - 1]          # use failure link to back the pattern up
        if P[q] == T[i]:
            q := q + 1
        if q == m:                 # full pattern match ending at index i
            matches.append(i - m + 1)
            q := f[q - 1]          # set up to find overlapping matches
    return matches

The two procedures are structurally identical — ComputeFailureFunction is essentially “match P against itself,” which is why the first thing KMP does is feed the pattern through its own search. That symmetry is the elegant part of the algorithm.

4. Python Implementation

def compute_lps(pattern: str) -> list[int]:
    """Build the LPS / failure function for `pattern`.
 
    f[i] = length of the longest proper prefix of pattern[:i+1]
           that is also a suffix of pattern[:i+1].
    """
    m = len(pattern)
    f = [0] * m
    k = 0  # length of the previous longest matching prefix
    for q in range(1, m):
        # Walk back along failure links until either the next char matches,
        # or we drop all the way back to k = 0.
        while k > 0 and pattern[k] != pattern[q]:
            k = f[k - 1]
        if pattern[k] == pattern[q]:
            k += 1
        f[q] = k
    return f
 
 
def kmp_search(text: str, pattern: str) -> list[int]:
    """Return all start indices (0-based) at which `pattern` occurs in `text`."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))            # every position matches the empty pattern
    f = compute_lps(pattern)
    matches = []
    q = 0                                     # number of pattern chars matched so far
    for i in range(n):
        # Use failure links to back up `q` until we can either match T[i] or reset to 0.
        while q > 0 and pattern[q] != text[i]:
            q = f[q - 1]
        if pattern[q] == text[i]:
            q += 1
        if q == m:                            # full match ending at index i
            matches.append(i - m + 1)
            q = f[q - 1]                      # allow overlapping matches
    return matches
 
 
# Worked example from §2:
assert compute_lps("ABABCABAB") == [0, 0, 1, 2, 0, 1, 2, 3, 4]
assert kmp_search("ABABDABACDABABCABAB", "ABABCABAB") == [10]

The q = f[q - 1] line after a full match is the bit most students miss. Without it, you’d find "ABAB" only once in "ABABABAB" (where it actually occurs three times, at indices 0, 2, 4). Setting q to the failure link of the last position keeps the matched prefix “alive” for overlap-detection.

5. Complexity — The Famous Amortized Argument

KMP is the textbook case study for amortized analysis in interviews. The casual observation “there’s a while loop inside a for loop, so it’s O(n·m)” is wrong, and the explanation of why is interview gold.

5.1 The potential-function argument

Define a potential function Φ = q (the current value of the pattern-pointer). The potential starts at 0 and is always non-negative.

For each iteration of the outer for loop (one text character T[i]):

  1. The while loop performs some number of q ← f[q-1] jumps. Each jump strictly decreases q by at least 1 (because f[q-1] < q for any q > 0 — the LPS is a proper prefix, so its length is strictly less). Each jump therefore decreases Φ by ≥ 1.
  2. The optional q ← q + 1 after a successful match increases Φ by exactly 1.

Total potential increases across the entire search: Φ goes up at most once per outer iteration, so the total number of increments across all n outer iterations is at most n.

Φ starts at 0, ends at some value ≥ 0. So:

total_decrements ≤ total_increments + initial_Φ − final_Φ ≤ n + 0 − 0 = n

Each while-loop iteration is one decrement. So the total work done by the while loop, summed across all n iterations of the for loop, is at most n. The for-loop body itself does O(1) work outside the while. Total time: O(n).

The same argument applied to ComputeFailureFunction (replacing n with m) gives O(m). Combined: O(n + m).

5.2 The space cost

  • f array: O(m).
  • A few scalars (i, q, n, m): O(1).
  • Total: O(m) auxiliary space (in addition to the inputs).

5.3 Why “no backtracking on T” matters

The text pointer i is monotonically non-decreasing — it never moves backwards. This means KMP can be applied online to a text arriving as a stream, with no need to buffer past characters. Naive search and even Boyer-Moore can require revisiting earlier text characters; KMP cannot. For network-protocol parsing, log-stream pattern matching, or DFA-style I/O pipelines, this property alone justifies the algorithm.

6. Variants and Extensions

6.1 Z-array equivalence

The Z-array (see Z-Algorithm) carries the same information as the failure function, just packaged differently. Both run in O(n) and can be derived from each other in O(n). Use whichever is more natural for your problem; the Z-array is often easier to reason about for “match prefix at position i” questions, while the failure function is easier for incremental DFA construction.

6.2 KMP automaton

The failure function lets you build a deterministic finite automaton with m + 1 states that recognises all occurrences of P. Each state has |Σ| outgoing transitions (one per alphabet character), giving O(m·|Σ|) construction time and O(1) per text-character match. This is what’s used in many regex engines for fixed-string components.

6.3 Aho-Corasick

Multi-pattern KMP: build a Trie of all patterns, then add KMP-style failure links between nodes that lead to a state corresponding to the longest proper suffix-that-is-a-prefix-of-any-pattern. Achieves O(n + Σ|Pᵢ| + matches) for searching n-character text against any number of patterns.

6.4 Strong KMP / Optimised failure links

The failure link sometimes points to a position whose character will also mismatch, requiring another jump. The “strong” failure function pre-computes through these chains, giving slightly fewer comparisons in the inner loop. The asymptotic complexity is unchanged but the constant factor improves on patterns with many repeats. cp-algorithms.com discusses this variant.

6.5 Number of distinct substrings

Using the failure function over all suffixes (or the equivalent Z-array trick), the count of distinct substrings of a length-n string can be computed in O(n²). The Suffix Array gives O(n log n) but is more complex to implement.

6.6 Period of a string

A useful folklore: the smallest period of P equals m − f[m−1] when m is divisible by (m − f[m−1]). (Intuition: if the longest proper suffix-prefix has length k, then P is the concatenation of copies of a length-(m−k) block.) This solves LeetCode 459 “Repeated Substring Pattern” in two lines after computing f.

7. Pitfalls

7.1 Off-by-one in the failure-function indexing

Different references use different conventions: 0-indexed f[i] for “LPS of P[0..i]”, 1-indexed f[i] for “LPS of P[1..i]”, and f[0] = -1 sentinel forms (CLRS uses this). They are not interchangeable; mixing the indexing of two references (e.g., copy-pasting one’s compute_lps with another’s search) silently produces a subtly wrong algorithm. Pick one convention and stay with it.

7.2 Forgetting q = f[q-1] after a full match

Without this line, KMP misses overlapping matches. "AAAA" searched for "AA" should find positions [0, 1, 2]; without the failure-link reset it finds only [0, 2].

7.3 Empty pattern

m = 0 is a degenerate case — different libraries return different things. Python’s str.find returns 0 for "".find(""). The convention in kmp_search above is to return all n + 1 insertion positions, matching how regex engines treat ^$. Match whatever your problem statement expects.

7.4 while k > 0 and P[k] != P[q]: vs while k >= 0 …

The CLRS pseudocode uses a -1 sentinel and does the comparison while k >= 0. The version above (which omits the sentinel) is cleaner but requires the explicit k > 0 guard. If you mix the two, you’ll either index P[-1] (Python wraps to the last character — silent bug) or infinite-loop.

7.5 Unicode / multi-byte characters

The algorithm is character-equality based and language-agnostic. In Python, text[i] over a str already gives Unicode code points. In C/C++, raw byte iteration over UTF-8 works for substring search but reports byte indices, not character indices. For interviews on Unicode strings, decode to a list of code points first.

7.6 Comparison count vs character-comparison count

KMP performs O(n + m) character comparisons. Library implementations (e.g., GNU string::find) sometimes use SIMD-accelerated naive search and beat KMP in wall-clock for short patterns despite worse asymptotic behavior — Mike Pall has well-known benchmarks. KMP’s win is worst-case linearity and the streaming property, not raw cycles on average inputs.

7.7 The f[m] extension

Many implementations allocate f[0..m] (one extra slot) to store the LPS of the full pattern, useful for the “period of a string” trick (§6.6) and for the q = f[q-1] re-entry after a full match. This is purely an indexing convention; it doesn’t change the algorithm.

8. Diagram — Failure-Link Jumps During Mismatch

flowchart LR
    Match["q characters of P matched against T[i-q..i-1]"]
    Mismatch{"P[q] vs T[i]"}
    Jump["q ← f[q-1] (jump back via failure link)"]
    NewMatch["resume at position q' < q in P, no rewind in T"]
    Forward["i ← i + 1"]
    Match --> Mismatch
    Mismatch -->|"equal"| Forward
    Mismatch -->|"not equal & q > 0"| Jump
    Jump --> Mismatch
    Mismatch -->|"not equal & q == 0"| Forward

What this diagram shows. The control flow at every text position. After matching q characters, we test P[q] against T[i]. On equality, we extend the match (q + 1) and advance i. On mismatch with q > 0, we don’t rewind i — we use the failure link f[q-1] to jump back to a shorter proper prefix of P that we already know matches the recent suffix of T, then re-test P[new q] vs T[i]. We may chain several failure-link jumps in a row (potentially down to q = 0) before the next text advance. The amortized analysis in §5 bounds the total number of these jumps across the entire run.

9. Common Interview Problems

LC# / SourceProblemUse of KMP
LC 28Implement strStr() / Find substringDirect KMP application
LC 459Repeated Substring PatternLPS-based period trick (§6.6)
LC 214Shortest PalindromeKMP on s + "#" + reverse(s) to find longest palindrome prefix
LC 686Repeated String MatchKMP applied after O(m)-bounded concatenation
LC 1392Longest Happy PrefixLPS of the whole string equals the answer (P[0..f[m-1]-1])
LC 3008Find Beautiful Indices in StringTwo simultaneous KMPs to find pattern positions in s
Codeforces 471DMUH and Cube WallsKMP on the difference sequence to match shapes

10. Open Questions

  • Is there a clean way to teach the amortized argument without invoking potential functions? Aggregate analysis works but feels ad-hoc; the potential method is cleaner but heavier prerequisites.
  • When does Boyer-Moore-Horspool actually beat KMP in practice? Empirically Boyer-Moore wins on short patterns and large alphabets; KMP wins on long patterns with high repetition.
  • Is there a parallel/SIMD KMP variant that achieves sub-linear wall-clock work? The data dependencies in the failure function seem fundamental.

11. See Also

Graph View

Backlinks