KMP Algorithm Explained: Building the Failure Table Step by Step

Knuth–Morris–Pratt is the string search that never goes backwards in the text. That property is easy to state and hard to believe until you have built the one piece that makes it possible: a table with one small number per character of the pattern, usually called the failure table or the LPS array.

Most confusion about KMP is really confusion about that table — what the numbers mean, and why the construction loop falls back to table[k - 1] instead of starting over. This article builds it slowly, then uses it to search, and counts the comparisons to show the guarantee is real.

The problem it solves

Find every occurrence of a pattern of length m in a text of length n.

The naive approach tries every starting position and compares character by character. On ordinary text it is fine, because mismatches come quickly. On repetitive input it is not: search for fifty as followed by a b inside ten thousand as, and nearly every one of the ten thousand starting positions compares fifty characters before failing. That is O(n × m), and the waste is obvious in hindsight — after matching fifty as, you already know what the next forty-nine characters of the text are.

KMP keeps that knowledge. When a match breaks, it asks: of what I have just matched, how much could still be the beginning of a new match?

The intuition

A border of a string is a proper prefix that is also a suffix. abab has the border ab: it starts with ab and ends with ab. ababa has two, a and aba, and the longest is aba.

The failure table stores, for each position i, the length of the longest border of the pattern's first i + 1 characters. For ababaca:

• a → 0, ab → 0, aba → 1, abab → 2, ababa → 3, ababac → 0, ababaca → 1

Why this is exactly the information a search needs: suppose you have matched ababa and the next text character is not c. The last five text characters are ababa. Its longest border is aba, so the last three text characters are also the first three characters of the pattern. You can carry on as if you had matched aba, without moving back in the text at all.

Building the table uses the same idea on the pattern itself. Keep k, the length of the border found so far. For the next character:

1. If it equals p[k], the border grows by one: k + 1.
2. If not, you need a shorter border that can be extended. The next candidates are the borders of the current border — any border of p[:k] is also a border of the current prefix, because p[:k] appears at both ends. The longest of those is table[k - 1]. Fall back to it and try again.
3. If k reaches 0 and still no match, the border here is 0.

The key fact in step 2 is that borders nest. You never need to search for the next-best border; the table already holds it.

Watch it run

The animation builds the table for ababaca. The band under the pattern marks the border being claimed — the prefix and the suffix of the same length — so you can check each number by eye. Watch position 5, the c: the border of length 3 cannot be extended, the fallback tries length 1, that fails too, and the entry becomes 0.

The code

The table, the search built on it, and a naive search for comparison. Both searches count character comparisons:

def failure_table(p):
    table = [0] * len(p)                # table[i] = longest border of p[:i+1]
    k = 0
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = table[k - 1]            # fall back to the border of the border
        if p[i] == p[k]:
            k += 1
        table[i] = k
    return table

def kmp_search(text, p):
    table, hits, k, compares = failure_table(p), [], 0, 0
    for i, ch in enumerate(text):       # i never moves backwards
        while k and ch != p[k]:
            compares += 1
            k = table[k - 1]
        compares += 1
        if ch == p[k]:
            k += 1
        if k == len(p):
            hits.append(i - k + 1)
            k = table[k - 1]            # keep going: matches may overlap
    return hits, compares

def naive_search(text, p):
    hits, compares = [], 0
    for s in range(len(text) - len(p) + 1):
        for j in range(len(p)):
            compares += 1
            if text[s + j] != p[j]:
                break
        else:
            hits.append(s)
    return hits, compares

print(failure_table("ababaca"))                 # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("abababacaba", "ababaca"))     # ([2], 12)
text, p = "a" * 10_000 + "b", "a" * 50 + "b"
print(kmp_search(text, p)[1], naive_search(text, p)[1])   # 19951 507501

On the repetitive input the naive search makes about twenty-five times as many comparisons, and the gap grows with the pattern length. KMP stays under 2n.

The table-building loop is the classic place for an off-by-one, so it is checked against the definition — try every border length and keep the longest that fits — and the search is checked against the naive one, along with the 2n bound:

import random

def borders_brute(p):                   # try every length, keep the longest that fits
    return [max(L for L in range(i + 1) if p[:L] == p[i + 1 - L:i + 1] and L <= i)
            for i in range(len(p))]

random.seed(6)
ok = True
for _ in range(4000):
    p = "".join(random.choice("ab") for _ in range(random.randint(1, 8)))
    t = "".join(random.choice("ab") for _ in range(random.randint(0, 40)))
    hits, compares = kmp_search(t, p)
    ok &= failure_table(p) == borders_brute(p)
    ok &= hits == naive_search(t, p)[0] and compares <= 2 * len(t)
print(ok)                                       # True

A two-letter alphabet is deliberate: it is the input where borders are most common and fallbacks chain the deepest.

The complexity

The while loop looks like it could make the search quadratic. It cannot. k goes up by at most one per text character, and every fallback lowers it by at least one. Since k never drops below zero, the total number of fallbacks over the whole search is at most n. So the search makes at most 2n comparisons: O(n). The same argument makes the table O(m), for O(n + m) in total and O(m) extra memory.

This is an amortised bound. A single text character can trigger several fallbacks; what is bounded is the total.

Where it goes wrong

• Resetting k to 0 on a mismatch. That is the naive search with extra steps. The fallback must be table[k - 1], repeatedly.
• Starting the build at i = 0. A one-character prefix has no proper border; comparing p[0] with itself sets table[0] to 1 and every later entry is wrong.
• Forgetting overlaps. After a full match, fall back to table[m - 1] rather than 0. Otherwise searching aa in aaaa finds 2 matches instead of 3.
• Confusing conventions. Some texts shift the table by one and store −1 at the start. Both work; mixing them does not.

For the intuition that comes before the table — why a mismatch should shift the pattern and by how much — see string matching intuition.

How to say it in an interview

"I precompute, for every prefix of the pattern, its longest proper prefix that's also a suffix. During the search, when a character mismatches after matching k characters, I don't move back in the text; I set k to the table value for k − 1, because that much of the pattern is still matched. k rises by at most one per character and every fallback lowers it, so the total work is O(n + m)."

Then write the build loop and the search loop next to each other. They are the same loop, and pointing that out shows you understand why the table works rather than having memorised it.