KMP & the Failure Function

What KMP solves

Find every occurrence of a pattern of length m inside a text of length n. The naïve algorithm slides the pattern across the text and compares character-by-character; on a partial match it advances the text pointer by one and starts over from the beginning of the pattern. In the worst case (pattern aaaab in text aaaaaaaaab) this is O(n·m). KMP achieves O(n + m) deterministic, no probability of failure, no hashing.

The failure function

Define fail[i] as the length of the longest proper prefix of pattern[0..i+1) that equals a suffix of pattern[0..i+1). "Proper" excludes the whole substring itself.

For pattern = "ABABABC":

i      pattern[0..i+1]   fail[i]
0      A                 0      (no proper prefix that is a suffix)
1      AB                0
2      ABA               1      (A matches A)
3      ABAB              2      (AB matches AB)
4      ABABA             3      (ABA matches ABA)
5      ABABAB            4      (ABAB matches ABAB)
6      ABABABC           0      (C breaks every continuation)

Reading the table: at position 5, fail[5] = 4 means the longest prefix of ABABAB that's also a suffix is ABAB (length 4). At position 6, the trailing C destroys every prefix-suffix overlap, so fail[6] = 0.

Building the failure function

The construction has the same shape as the matching loop, a "compare; on mismatch, fall back via fail[]; on match, advance" structure. Two pointers: i walks the pattern from left to right; k tracks the length of the current longest prefix-suffix match.

def build_failure(pattern):
    fail = [0] * len(pattern)
    k = 0                                 # length of current prefix-suffix
    for i in range(1, len(pattern)):
        while k > 0 and pattern[k] != pattern[i]:
            k = fail[k - 1]               # fall back
        if pattern[k] == pattern[i]:
            k += 1
        fail[i] = k
    return fail

The outer loop walks i. The inner while falls back via fail[k − 1] until either the characters match or k reaches 0. Each fallback strictly decreases k, and k can only increase by 1 per outer iteration, so across the whole construction, the total work is O(m), not O(m²).

The fallback is the algorithm's heart. When pattern[k] != pattern[i], we don't reset k to 0, that would throw away progress. Instead, we look up the longest prefix-suffix shorter than k that we've already verified. fail[k − 1] gives exactly that.

The matching loop

Identical structure: walk the text with i, track the length of the current pattern-prefix match with j. On mismatch, fall back via fail[j − 1]. On match, advance j; if j reaches the pattern's length, we have a full match.

def kmp_search(text, pattern):
    if not pattern: return [0]
    fail = build_failure(pattern)
    matches = []
    j = 0
    for i in range(len(text)):
        while j > 0 and pattern[j] != text[i]:
            j = fail[j - 1]
        if pattern[j] == text[i]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = fail[j - 1]               # continue searching for overlapping matches
    return matches

Notice that the text pointer i never moves backward, the for-loop only advances. The pattern pointer j can fall back, but each fallback strictly decreases it, and increases happen at most once per text character. By the same amortised argument as the construction, total work is O(n).

A worked trace

Search for ABABC in ABABABC. First, the failure function:

pattern  A  B  A  B  C
fail     0  0  1  2  0

Now matching:

i  text[i]  j_before  match?  j_after
0  A        0         A==A    1
1  B        1         B==B    2
2  A        2         A==A    3
3  B        3         B==B    4
4  A        4         A!=C    fall back: j = fail[3] = 2
                      A==A    3
5  B        3         B==B    4
6  C        4         C==C    5  ← full match at i - 4 = 2

Found at position 2. The text pointer never moved backward; we only consulted fail[3] to find that AB is the longest prefix-suffix consistent with what we'd already seen, and resumed from there.

Complexity, reasoned

Building the failure function: O(m). The amortised argument is that k increases at most once per outer iteration (m times total) and each fallback decreases it by at least 1. The total number of fallbacks is bounded by the total increases, so the inner loop runs at most m times across the whole construction.

Matching: O(n) by the same argument applied to j. Total: O(n + m). Memory: O(m) for the failure table.

When KMP, when Rabin-Karp

KMP and Rabin-Karp both achieve O(n + m) for single-pattern matching. Choose KMP when:

• You need deterministic performance, adversarial inputs cannot push KMP into worst case the way they can Rabin-Karp.
• You have memory constraints. KMP needs only O(m) for the failure table.
• The pattern is unlikely to repeat across runs, building the failure function each time is fine.

Choose Rabin-Karp for multi-pattern matching, 2D matching, or when implementation simplicity matters.

Where the failure function reappears

Shortest palindrome

"Add the minimum number of characters to the front of s to make it a palindrome." Concatenate s + '#' + reverse(s) and compute the failure function. The last value tells you the longest palindromic prefix of s; everything before it must be reflected to the front. The '#' separator prevents the matching from spilling between halves.

Repeated-substring detection

"Is s made of repetitions of a smaller substring?" Compute fail; if the last fail[n−1] is greater than zero AND (n − fail[n−1]) divides n, then yes, and the smallest repeated unit has length n − fail[n−1].

Aho-Corasick

The natural generalisation: instead of a linear failure function, build a trie of all patterns and add failure links between nodes. Matches all patterns in one pass over the text. Used in grep -F, intrusion-detection systems, antivirus pattern engines.

Where beginners go wrong

• Off-by-one in the failure function. fail[i] uses indices into pattern[0..i+1). After a successful match incrementing k, fail[i] = k records the new value. Mixing up "prefix length" with "last matched index" by one position breaks everything.
• Resetting k to 0 on mismatch. Throws away all the progress encoded in fail. The fallback rule k = fail[k − 1] is what makes the algorithm linear.
• Forgetting overlapping matches. After a full match in the matching loop, set j = fail[j − 1] to find overlapping occurrences. Setting j = 0 misses overlaps like the second occurrence of aba in ababa.
• Confusing failure function with Z-function. Both are O(n) string-matching helpers but they encode different things. KMP's failure function is "prefix that is also a suffix"; Z is "longest substring starting here that matches a prefix of the whole string". Don't paste one into the other.

What to read next

The Rolling Hash & Rabin-Karp deep-dive is the canonical alternative, same asymptotic, very different implementation. The Strings module connects KMP to a wider family of pattern algorithms (Boyer-Moore, suffix arrays, Aho-Corasick).