KMP and the Failure Function

In short: KMP precomputes a failure function π, the longest border (a proper prefix that is also a suffix) of every prefix of the pattern, in O(m). On a mismatch the search falls back to the next shorter border instead of restarting, so the text pointer never moves backwards and the whole search is O(n) worst case, guaranteed — unlike Rabin-Karp's hash gamble or the naive scan's O(n · m).

The pattern abcab matched 5 characters then failed; its border ab lets it slide to start 3 and keep reading forward from the same text position

Rabin-Karp makes the windows that don't match cheap, but it is still a gamble. A collision costs a wasted check, and a text full of genuine near-misses can still cost n · m. Quarry has a harder requirement too: it tails live logs. Text arrives a chunk at a time, and once a chunk has gone past, Quarry can't read it again. A matcher that backs up to "try the next alignment" is useless there.

The Knuth-Morris-Pratt algorithm (KMP) fixes both problems. It is exact, it is O(n + m) in the worst case, and its text pointer never moves backwards. The idea behind it is that the naive search keeps throwing away something it already knows.

What the naive search forgets

Search for abcabd in abcabcabd. The first five characters match, and then the text's c meets the pattern's d. The naive search slides the pattern one place right and starts reading again from text index 1.

But at that moment you know the last five text characters: they are abcab, because they just matched the pattern. So you don't need the text to decide which alignments could still work. An alignment can only succeed if the start of the pattern lines up with the end of what you've already matched, which means a prefix of the pattern has to equal a suffix of abcab. The longest such overlap is ab. So slide the pattern until its ab sits under the text's last ab, and carry on from the same text position.

Borders

A border of a string is a proper prefix that is also a suffix. "Proper" means shorter than the whole string.

abcab has one border: ab.
aaaa has three: aaa, aa and a.
abcd has none, only the empty string.

What does this print?

s = "abacaba"
best = 0
for k in range(1, len(s)):
    if s[:k] == s[-k:]:
        best = k
print(best)

The failure function (also called the prefix function) stores, for every prefix of the pattern, the length of its longest border:

\pi[i] = \text{length of the longest border of } p[0..i]

For abcabd it is [0, 0, 0, 1, 2, 0]. The 2 under the second b is the ab you just found, and it tells the matcher: if you fail after matching five characters, you still have two.

Here is that search, with the pattern drawn under the text at its current alignment:

watch it move · grid

On a mismatch the pattern slides by the failure function, not by one, and the text pointer never moves back.

i = 0, j = 0: text a meets pattern a. They match, so both pointers move right. 2 by 9 table. At row 0, column 0 — value a. 15 of 18 cells filled.

1 / 6

The search loop

The code is short. j is how many pattern characters are currently matched. On a mismatch, fall back through the borders until the next character can extend one, or until j hits 0:

python

After a full match, j = pi[j - 1] doesn't start again from zero. It keeps the longest border of the whole pattern, so overlapping occurrences are found too:

What does this print?

def kmp(text, p):
    pi, j = [0] * len(p), 0
    for i in range(1, len(p)):
        while j and p[i] != p[j]:
            j = pi[j - 1]
        j += p[i] == p[j]
        pi[i] = j
    hits, j = [], 0
    for i, ch in enumerate(text):
        while j and ch != p[j]:
            j = pi[j - 1]
        j += ch == p[j]
        if j == len(p):
            hits.append(i - j + 1)
            j = pi[j - 1]
    return hits

print(kmp("aaaaa", "aa"))

Building the failure function

The failure function is itself a matching problem: the pattern searched against itself. j tracks the longest border of the prefix so far. At each new character, either it extends that border by one, or you fall back to the border of the border and try again. Step through a small one:

step through it

1p = "abab"

2pi = [0] * len(p)

3j = 0

4for i in range(1, len(p)):

5 while j > 0 and p[i] != p[j]:

6 j = pi[j - 1]

7 if p[i] == p[j]:

8 j += 1

9 pi[i] = j

10print(pi)

The fallback has to be a while, not an if. One step back isn't always enough, because the next shorter border may not extend either:

broken — fix it

No proper prefix of dadadx ends in x, so π[5] must be 0. This prints 1.

Now build it yourself and watch the table fill in. Each frame shows the character row, the π row, and the two characters being compared. Try "aabaaab", "abcd" and "aaaa", or put the if bug back in and watch a wrong value appear:

your code, drawn · grid

Your failure function, one entry per frame. A mismatch falls back through shorter borders, and a match extends the current one by exactly one.

Why it's O(n + m)

The while loop inside the for loop looks like it could be O(n · m). It isn't. Count how j moves:

each text character raises j by at most 1, so over the whole text j rises at most n times in total;
each fallback lowers j by at least 1, and j never goes below 0.

You can't lower something more times than you raised it, so all the fallbacks together cost at most n. The search makes at most 2n comparisons, and the same argument gives 2m for building π. This is an amortised bound: one character can trigger several fallbacks, but only by spending rises that earlier characters paid for.

The naive search's worst case is about $m \cdot n$ comparisons for a pattern of length $m$ , against KMP's guarantee of $2n$ . Only when $m \le 2$ is naive never worse. For any real query the naive worst case is $m/2$ times KMP's bound, so a 40-character pattern can cost twenty times as much. The gap grows with the pattern, and KMP's bound doesn't depend on it at all.

❓ Cross-question — "If KMP is always linear, why does Python's str.find not use it?" CPython's search is a tuned hybrid. It skips ahead using the last character of the pattern and, for long needles, switches to a two-way algorithm that also guarantees linear time. On ordinary text the skipping wins. KMP's advantages are that it's simple to get right, it never re-reads the text, and its failure function answers questions find can't, like the ones below.

What π knows about a string

The last entry of π describes the whole string. If s has a border of length b, then s repeats itself with period len(s) − b: shift it that far and it lines up with itself.

python

An interview question. Quarry's log compactor stores a line as block × k when the line is an exact repetition of a shorter block. Given a line, return the shortest such block. The period from π answers it in O(n), provided it divides the length. abcabcab has period 3 but isn't a whole number of abcs, so it compacts to itself. That's the build exercise below.

What it costs

	naive	Rabin-Karp	KMP
preprocessing	none	O(m)	O(m) for π
worst-case search	O(n · m)	O(n · m)	O(n)
reads a text character again	yes	only to verify	never
can run on a stream	no	yes, with a window buffer	yes, keeps only `j`
extra memory	O(1)	O(1)	O(m) for π

Idioms & real-world patterns

while j > 0 and a != b: j = pi[j - 1] is the whole algorithm. It appears once for building π and once for searching.
j = pi[j - 1] after a full match finds overlapping occurrences. To skip overlaps, set j = 0 instead.
The state is one integer. Save j between chunks and the match carries on across chunk boundaries. That is what makes KMP a streaming matcher.
len(s) − π[-1] is the shortest period, used in compression and in tests for "is this string a repetition?".
Where it lives: intrusion-detection signatures scanned over network streams, the failure links of multi-pattern matchers, and the textbook example of an amortised O(n) algorithm.

⚡ Advanced — KMP as an automaton

For a small alphabet you can precompute, for every state j and every character c, the state you end up in. That turns the failure function into a finite automaton with m + 1 states, where each text character costs exactly one table lookup and there is no while loop at all. The table costs O(m · alphabet) to build, which is fine for DNA's four letters and wasteful for Unicode.

Quick practice

What does this print?

s = "abcabcab"
best = 0
for k in range(1, len(s)):
    if s[:k] == s[-k:]:
        best = k
print(best)

broken — fix it

π("aabaaab") should be [0, 1, 0, 1, 2, 2, 3], but every entry here is 0 — j changes as the loop runs, it's just never saved.

🎯 Your turn

Build kmp_search(text, pattern), Quarry's streaming matcher. Build the failure function, then make one forward pass over text and return every start index where pattern occurs, in order, overlaps included. An empty pattern returns [].

kmp_search("abcabcabd", "abcabd") → [3]
kmp_search("aaaaa", "aa") → [0, 1, 2, 3]

Then press ▶ Run, tap the Live App try chips, and hit ✓ Check.

KMP and the Failure Function

KMP and the Failure Function

What the naive search forgets

Borders

The search loop

Building the failure function

Why it's O(n + m)

What π knows about a string

What it costs

Idioms & real-world patterns

⚡ Advanced — KMP as an automaton

Quick practice

🎯 Your turn

Practice — level up