Knuth-Morris-Pratt, Derived Rather Than Memorized

When a character comparison fails, you have already learned a lot — you just have to listen to what you learned. KMP is what you get when you take that listening seriously.

The Naive Algorithm and Its Wound

Given a pattern $P$ of length $m$ and a text $T$ of length $n$, the textbook plan is to slide $P$ over $T$ one position at a time, comparing character by character at each alignment. If they all match, record an occurrence; if any disagree, shift by one and start over.

def naive(t, p):
    out = []
    for i in range(len(t) - len(p) + 1):
        if all(t[i + j] == p[j] for j in range(len(p))):
            out.append(i)
    return out

This works. It is also $O(nm)$ in the worst case, and the worst case is not exotic. With $T = \texttt{aaaaaaaab}$ and $P = \texttt{aaab}$ we match three $\texttt{a}$s, fail at the $\texttt{b}$, shift by one, and re-prove the same equalities all over again. We threw away knowledge. That is the wound.

KMP, published as Knuth, Morris, and Pratt, Fast Pattern Matching in Strings, SICOMP 6 (1977), heals it. The compact code and the famous "failure function" both look mysterious if you meet them as finished objects. They stop being mysterious if you let them grow from one observation.

The Observation

Suppose the naive algorithm is at text position $i$ and has just matched the first $j$ characters of $P$. Then it has discovered

The next text character $T[i]$ is what broke the match: $T[i] \neq P[j]$. The naive response is to discard all of that and restart at text position $i - j + 1$ with no progress. But we know those $j$ characters — they are a copy of $P[0\,..\,j-1]$. So whatever the right next alignment is, it depends on $P$ alone.

Concretely: if we shift $P$ to the right by $j - k$ positions, the first $k$ characters of $P$ must agree with the last $k$ characters of the matched block. The matched block is $P[0\,..\,j-1]$, so the requirement is

a proper prefix of $P[0\,..\,j-1]$ equal to a suffix of the same string. We want the largest such $k$, because that gives the smallest legal shift and we already know every smaller shift is invalid (the matched block tells us so). Then we resume by comparing $T[i]$ against $P[k]$ — without ever re-examining $T[i-j..i-1]$.

That $k$ is a function of $P$ and $j$ only. Precompute it.

The Failure Function

Define, for each $q \in \{0, 1, \dots, m-1\}$,

with the empty prefix as the $k = 0$ fallback. In words: $\pi[q]$ is the length of the longest proper prefix of $P[0\,..\,q]$ that is also a suffix. This $\pi$ is properly the Morris–Pratt prefix function; Knuth's refinement is to compute a strong failure function, one that redirects any failure link whose target character would only reproduce the comparison that just failed — i.e. where $P[\pi[q]] = P[q+1]$ — onward to the next link in the chain, saving a guaranteed-doomed retry.

Worked example for $P = \texttt{ababaca}$:

The rule of use: when we have matched $j$ characters and the next comparison fails, we set $j \leftarrow \pi[j-1]$ and try the same text character against the new $P[j]$. We may need to apply this several times in a row (each step strictly decreases $j$), stopping either when $P[j]$ matches the current character or when $j = 0$.

A useful picture is as an automaton. States $0, 1, \dots, m$ record how many characters of $P$ we have matched so far; state $m$ is accept. Solid forward arrows are the matching transitions labelled by the pattern's characters; back-arrows are the failure links $q \mapsto \pi[q-1]$ that fire on a mismatch. For $P = \texttt{aabaab}$ the picture looks like this:

Notice the self-similarity: the back-arrows from states $4, 5, 6$ point at $1, 2, 3$ — the same offsets, shifted by the repeat. We'll exploit exactly that to compute $\pi$ itself.

Matching, Once $\pi$ Is in Hand

def kmp_search(t, p):
    if not p:
        return list(range(len(t) + 1))
    pi = failure(p)
    j, out = 0, []
    for i, c in enumerate(t):
        while j > 0 and p[j] != c:
            j = pi[j - 1]
        if p[j] == c:
            j += 1
        if j == len(p):
            out.append(i - j + 1)
            j = pi[j - 1]
    return out

The outer for loop walks $T$ left to right and never backtracks — that is the entire point. The inner while is the failure cascade: it keeps replacing $j$ by $\pi[j-1]$ until either $P[j]$ matches the current character or $j$ has fallen to $0$.

Trace on $T = \texttt{ababcabab}$, $P = \texttt{abab}$, with $\pi = [0, 0, 1, 2]$:

• $i=0$: a matches $P[0]$, $j=1$.
• $i=1$: b matches $P[1]$, $j=2$.
• $i=2$: a matches $P[2]$, $j=3$.
• $i=3$: b matches $P[3]$, $j=4$. Record match at position $0$. Reset $j \leftarrow \pi[3] = 2$.
• $i=4$: c vs $P[2]=$a. Fail. $j \leftarrow \pi[1] = 0$. c vs $P[0]=$a. Fail, $j$ stays $0$.
• $i=5$: a matches $P[0]$, $j=1$. ... eventually $j=4$ at $i=8$, recording match at position $5$.

At $i=4$ we never went back in $T$ and we never re-tested $T[2], T[3]$. That is the linear-time payoff in action.

Computing $\pi$ With KMP Itself

The recurrence for $\pi$ is the same dance, run with $P$ playing the role of both pattern and text:

def failure(p):
    pi = [0] * len(p)
    k = 0
    for q in range(1, len(p)):
        while k > 0 and p[k] != p[q]:
            k = pi[k - 1]
        if p[k] == p[q]:
            k += 1
        pi[q] = k
    return pi

Why does this work? Suppose we have $\pi[0], \dots, \pi[q-1]$ and want $\pi[q]$. The candidate lengths $\ell$ for $\pi[q]$ are exactly those for which $P[0\,..\,\ell-2]$ is already a prefix-and-suffix of $P[0\,..\,q-1]$ and the next character agrees: $P[\ell - 1] = P[q]$. The set of prefix-suffix lengths of $P[0\,..\,q-1]$ is precisely

a strictly decreasing chain that ends at $0$. We walk it (the while loop) until $P[k] = P[q]$, then extend by one. If we exhaust the chain, $\pi[q] = 0$.

It is the same observation reapplied. When you're computing $\pi$, the "text" is the pattern.

Why the Whole Thing is Linear

The runtime claim is $O(n + m)$ despite the inner while-loops. The cleanest proof is an amortized potential argument.

For the matching loop, let $\Phi = j$, the current number of matched characters. Then for one pass of the outer for:

• The while loop replaces $j$ by $\pi[j-1] \le j - 1$, so each iteration decreases $\Phi$ by at least $1$.
• The trailing if and the post-match reset together change $j$ by at most $+1$.
• The actual work in this pass is $1 + w$, where $w$ is the number of while iterations.

Define amortized cost $\hat c = c + \Delta\Phi$. Then $\hat c \le (1 + w) + (1 - w) = 2$. So the amortized cost per outer iteration is $O(1)$, the total amortized cost over $n$ outer iterations is $O(n)$, and since $\Phi \ge 0$ throughout, the actual total is also $O(n)$. The same argument with $k$ in place of $j$ gives $O(m)$ for failure. Grand total: $O(n + m)$.

A more humane way to read the bound: every while decrement has been pre-paid by an earlier successful match that incremented $j$, and you can't decrement more often than you incremented. The fast inner loop is fast because the outer loop is slow enough to fund it.

What's Proved, What's Asserted, Where to Go Next

Proved above:

• $\pi$, by its definition, gives the smallest shift consistent with everything already matched, so the algorithm never misses an occurrence and never reports a phantom one.
• The total running time is $O(n + m)$ by the potential argument.

Asserted but standard: the original KMP paper gives a finite-automaton variant in which the transitions are pre-resolved over the alphabet $\Sigma$, taking $O(m|\Sigma|)$ table space in exchange for one transition per text character with no failure cascades. The failure-function version costs only $O(m)$ space; the cascades are amortized away as above. Aho and Corasick (CACM 1975) generalize the same construction to a set of patterns by building a trie and decorating it with failure links computed by a single breadth-first pass.

Open or context-dependent: KMP is not always the fastest in practice. Boyer–Moore and its descendants — most directly Boyer–Moore–Horspool — often win on long patterns and large alphabets because their bad-character and good-suffix heuristics can skip multiple text characters at once, and KMP cannot. (Not every fast library matcher is a Boyer–Moore relative: glibc's memmem and strstr use the Two-Way algorithm of Crochemore and Perrin, built on critical factorization, and the default libstdc++ std::search is the naive $O(nm)$ scan — Boyer–Moore is opt-in there via std::boyer_moore_searcher.) KMP's selling point is its guarantee: linear time, no input pathology, fully forward-only access to the text. For streaming data that you cannot rewind, for adversarial inputs, or for tight worst-case bounds in a real-time system, that guarantee is the whole game.

The thing worth keeping is not the code. It is the observation in the second section: when a comparison fails, you already hold a piece of $P$ in your hand, drawn from $T$. The right next move depends on $P$ alone. Once you commit to that, the failure function, the matching loop, and the recursive trick that computes $\pi$ are forced moves, not flashes of brilliance.