KMP Algorithm

The naive matcher’s sin was resetting to zero after a mismatch, re-reading text it had already seen. KMP makes a bold claim: when a match fails partway through the pattern, you can always figure out exactly where to resume — using only the pattern, computed before you ever touch the text — so the text pointer never moves backward. The question is: where does it resume? Answering that for every position is the failure function, and it’s the whole algorithm.

The Knuth-Morris-Pratt algorithm (1977) solves the pattern-matching problem in O(n + m) time — O(m) to preprocess the pattern, O(n) to scan the text — with a guarantee that the text pointer never moves backward. Every character is read at most twice.

The key insight: when a mismatch occurs at T[i] vs P[j], we don’t need to reset j to 0. We can reset j to a smaller value — the length of the longest proper prefix of P[0..j-1] that is also a suffix. That value is precomputed for every j and stored in an array called the failure function (also called the prefix function, or lps for “Longest Proper Prefix which is also Suffix”).

The failure function

For a pattern P of length m, define fail[j] as the length of the longest proper prefix of P[0..j] that is also a suffix of P[0..j].

“Proper” means strictly shorter than the whole string — we don’t count P[0..j] itself.

Example: P = "ABABCABAB"

The pattern fail = [0, 0, 1, 2, 0, 1, 2, 3, 4].

Building the failure function

The failure function can be built in O(m) using the observation that fail[j+1] can be derived from fail[j]:

def build_fail(P):
    m = len(P)
    fail = [0] * m
    k = 0                         # length of current matching prefix
    for j in range(1, m):
        while k > 0 and P[k] != P[j]:
            k = fail[k - 1]       # fall back
        if P[k] == P[j]:
            k += 1
        fail[j] = k
    return fail

There’s one line that makes this self-referential and confuses everyone the first time. When P[k] != P[j], we can’t just give up — we fall back to the next-shorter prefix-that-is-also-a-suffix and try again. Which line does the fall-back?

def build_fail(P):
  m = len(P)
  fail = [0] * m
  k = 0                         # length of current matching prefix
  for j in range(1, m):
      while k > 0 and P[k] != P[j]:
          # ??? fall back to the longest prefix-suffix of the shorter prefix
      if P[k] == P[j]:
          k += 1
      fail[j] = k
  return fail

k = fail[k - 1] is the recursion that does everything: instead of restarting at k = 0, it jumps to the best shorter prefix-suffix and retries. This is KMP searching P inside itself.

The outer loop runs m - 1 times. The inner while loop decreases k by at least 1 each iteration, and k can only increase by 1 per outer loop step. So the total number of k decreases is bounded by the total increases — which is at most m - 1. Total work: O(m).

The KMP search

With fail precomputed, the search is clean:

def kmp_search(T, P):
    n, m = len(T), len(P)
    fail = build_fail(P)
    matches = []
    j = 0                          # characters matched so far
    for i in range(n):
        while j > 0 and T[i] != P[j]:
            j = fail[j - 1]        # fall back without moving i
        if T[i] == P[j]:
            j += 1
        if j == m:                 # full match
            matches.append(i - m + 1)
            j = fail[j - 1]        # continue searching for overlapping matches
    return matches

The text pointer i only moves forward. The pattern pointer j can move backward via fail, but the total backward movement is bounded by the total forward movement (same amortized argument as above). Total comparisons: at most 2n.

Walkthrough: T = "ABABCABABD", P = "ABABD"

Pattern fail = [0, 0, 1, 2, 0].

The critical moment is at step 5: after the mismatch at T[4]='C' vs P[4]='D', KMP doesn’t restart from T[1]. It knows that T[2..3] = "AB" = P[0..1] (because fail[3] = 2), so it resumes matching from P[2] — without re-reading any text. The text pointer never moved back.

Full implementation

vector<int> buildFail(const string& P) {
    int m = P.size();
    vector<int> fail(m, 0);
    int k = 0;
    for (int j = 1; j < m; j++) {
        while (k > 0 && P[k] != P[j]) k = fail[k - 1];
        if (P[k] == P[j]) k++;
        fail[j] = k;
    }
    return fail;
}
 
vector<int> kmpSearch(const string& T, const string& P) {
    int n = T.size(), m = P.size();
    auto fail = buildFail(P);
    vector<int> matches;
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && T[i] != P[j]) j = fail[j - 1];
        if (T[i] == P[j]) j++;
        if (j == m) {
            matches.push_back(i - m + 1);
            j = fail[j - 1];
        }
    }
    return matches;
}

def build_fail(P):
    m = len(P)
    fail = [0] * m
    k = 0
    for j in range(1, m):
        while k > 0 and P[k] != P[j]:
            k = fail[k - 1]
        if P[k] == P[j]:
            k += 1
        fail[j] = k
    return fail
 
def kmp_search(T, P):
    n, m = len(T), len(P)
    fail = build_fail(P)
    matches = []
    j = 0
    for i in range(n):
        while j > 0 and T[i] != P[j]:
            j = fail[j - 1]
        if T[i] == P[j]:
            j += 1
        if j == m:
            matches.append(i - m + 1)
            j = fail[j - 1]
    return matches

int[] buildFail(String P) {
    int m = P.length();
    int[] fail = new int[m];
    int k = 0;
    for (int j = 1; j < m; j++) {
        while (k > 0 && P.charAt(k) != P.charAt(j)) k = fail[k - 1];
        if (P.charAt(k) == P.charAt(j)) k++;
        fail[j] = k;
    }
    return fail;
}
 
List<Integer> kmpSearch(String T, String P) {
    int n = T.length(), m = P.length();
    int[] fail = buildFail(P);
    List<Integer> matches = new ArrayList<>();
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && T.charAt(i) != P.charAt(j)) j = fail[j - 1];
        if (T.charAt(i) == P.charAt(j)) j++;
        if (j == m) {
            matches.add(i - m + 1);
            j = fail[j - 1];
        }
    }
    return matches;
}

The amortized argument

The i pointer strictly increases — n increments total. The j pointer increases by 1 each time T[i] == P[j] (at most n times) and decreases via fail each mismatch. Since j can’t go below 0 and every decrease came from a prior increase, the total decreases are at most n. Total j movements: at most 2n. Total comparisons: at most 2n. KMP is O(n) for the search phase.

The preprocessing phase runs the same logic on P alone — O(m).

Grand total: O(n + m), O(m) space.

Applications beyond simple search

The failure function is powerful beyond pattern matching:

1. Does a string have a repeated structure?

A string s of length n is a repetition of a shorter string of length k if and only if k divides n and n % (n - fail[n-1]) == 0.

def smallest_period(s):
    fail = build_fail(s)
    n = len(s)
    k = n - fail[n - 1]
    return k if n % k == 0 else n

For s = "ABABABAB", fail[-1] = 6, k = 8 - 6 = 2. Since 8 % 2 == 0, the period is 2 ("AB").

2. Shortest palindrome by KMP on the reverse

To find the shortest palindrome that starts with s, concatenate s + '#' + reversed(s) and compute the failure function. fail[-1] gives the length of the longest prefix of s that is also a palindrome prefix (because it’s a prefix of s that matches a suffix of reversed(s)). This directly solves LeetCode #214 Shortest Palindrome.

3. Count of pattern occurrences in text including overlapping

The fail[j-1] at the end of a full match handles overlapping occurrences automatically. The kmp_search above already counts them correctly.

Complexity

Quick check

This is the introduction’s “never reset to zero” promise, made concrete: the failure function is the precomputed answer to “where do I resume?” Next: Rabin-Karp — a completely different bet. Instead of remembering the pattern’s structure, it turns each text window into a number and compares numbers in O(1), which is what unlocks multi-pattern search and duplicate-substring detection.