KMP & the failure function

Never re-compare a matched prefix: precompute borders and skip in O(n + m). · 12 min read

The key idea

When the naive scan mismatches after matching a prefix of P, it throws that work away. KMP (Knuth–Morris–Pratt) instead asks: how much of what I just matched is also a prefix of `P`? That overlap (a border) is exactly how far the pattern can safely slide without missing a match — so we never move the text pointer backward.

The failure function (prefix function)

For each position i, π[i] = the length of the longest proper prefix of P[0..i] that is also a suffix of it. It's precomputed in O(m) by matching the pattern against itself:

vector<int> prefix_function(const string& p) {
    int m = p.size();
    vector<int> pi(m, 0);
    for (int i = 1, k = 0; i < m; i++) {
        while (k > 0 && p[i] != p[k]) k = pi[k - 1];
        if (p[i] == p[k]) k++;
        pi[i] = k;
    }
    return pi;
}

Matching with the table

Scan the text once. Keep j = how many pattern characters currently match. On a mismatch, jump j = π[j-1] (slide the pattern using its border) instead of restarting. The text index never goes backward, so it's linear.

Interactive visualization: KMP: skip ahead with the failure function — step through it frame by frame on this page.

KMP is linear

build π in O(m) — Self-match of the pattern.
scan text, i never moves back — Each char advances i or shrinks j.
O(n) for the scan — Amortised over j's increases/decreases.

Result: O(n + m) time, O(m) space

Rolling hash (Rabin–Karp)

Another approach: hash the pattern and every length-m window of the text. A rolling hash updates the window hash in O(1) as it slides (remove the leaving char, add the entering one), giving O(n + m) average time. Verify on a hash hit to avoid false positives. It generalises nicely to 2D and multi-pattern search.

Practice: Longest Happy Prefix (Hard) — Longest proper prefix that is also a suffix — the KMP failure value.