KMP Algorithm — Linear String Matching With Failure Function

The architecture

Failure function: for each position in the pattern, the length of the longest proper prefix that's also a suffix. Computed in O(m) with a two-pointer scan of the pattern.

Search: walk through text with a pattern pointer. On mismatch, use failure function to reset pattern pointer without moving text pointer back.

The naive matcher and the exact input that breaks it

The obvious way to find a pattern of length m inside a text of length n is to try every alignment. Put the pattern at offset 0, compare left to right until a character disagrees, then slide the pattern one position right and start over from the pattern's first character. It is four lines of code and it is correct.

def naive_search(text, pat):
    n, m = len(text), len(pat)
    for i in range(n - m + 1):
        k = 0
        while k < m and text[i + k] == pat[k]:
            k += 1
        if k == m:
            yield i

On English prose this is fast. The inner while almost always dies on its first comparison, because a randomly chosen text character matches a randomly chosen pattern character with probability roughly 1/26, so the expected work per alignment is a shade over one comparison and the whole scan costs about n comparisons.

The worst case is not random, though, and it is easy to construct. Take text = "aaaa...a" of length n and pat = "aaa...ab" - m - 1 copies of a followed by a single b. Every alignment matches m - 1 characters and then fails on the last one. That is (n - m + 1) x m character comparisons. With n = 1,000,000 and m = 1,000 that is close to a billion comparisons for zero matches. The structural problem is not the comparison count per alignment; it is that after failing at offset i, the naive matcher throws away everything it just learned and re-reads text[i+1 .. i+m-1] from scratch. It already knows those characters. KMP is the observation that you never need to read a text character twice.

The prefix function - what pi[i] actually means

The whole algorithm hangs on one array, computed from the pattern alone, before you ever look at the text. Call it pi (also written as the failure function, or the border array).

Definition. pi[i] is the length of the longest proper prefix of pat[0..i] that is also a suffix of pat[0..i].

Every word in that sentence is load-bearing. Proper means strictly shorter than the string itself - drop it and the answer is trivially i + 1, because every string is its own prefix and its own suffix. Both the prefix and the suffix are taken from the same slice pat[0..i], not from the full pattern: pi is an array of answers about growing prefixes of the pattern, one entry per position. Such a string that is simultaneously a proper prefix and a proper suffix is called a border, so pi[i] is the length of the longest border of pat[0..i].

For pat = "ababaca":

Read pi[4] = 3 as: the prefix ababa has aba as both a proper prefix and a proper suffix, and nothing longer works. pi[5] = 0 because ababac ends in c and the pattern starts with a, so no border of any length survives.

The reason this is the right object to precompute: suppose you have matched j characters of the pattern against the text and the next character disagrees. Sliding the pattern right by one is almost always wasted work, because for the pattern to match at that new offset, its prefix would have to coincide with a suffix of what you already matched. The longest such coincidence is exactly pi[j-1]. So the correct move is: keep the text pointer where it is, and set the pattern pointer to pi[j-1].

Building the table in O(m) - the self-matching argument

The build is KMP's search loop run with the pattern as both the text and the pattern. That is not an analogy; it is literally the same code with one index offset.

def prefix_function(pat):
    m = len(pat)
    pi = [0] * m
    k = 0                       # length of the border we are currently extending
    for i in range(1, m):
        while k > 0 and pat[i] != pat[k]:
            k = pi[k - 1]       # fall back to the next shorter border
        if pat[i] == pat[k]:
            k += 1
        pi[i] = k
    return pi

The invariant at the top of each iteration is that k == pi[i-1]: the longest border of the prefix ending at i-1. To extend it to position i, you need pat[i] == pat[k]. If it holds, the border grows by one and pi[i] = k + 1.

If it does not hold, the key insight is that the next candidate border length is not k - 1. Any shorter border of pat[0..i-1] is itself a border of the border - the set of all border lengths of a string is exactly the chain pi[i-1], pi[pi[i-1]-1], pi[pi[pi[i-1]-1]-1], ... down to 0. So k = pi[k-1] jumps straight to the next viable candidate and skips every length that could not possibly work. That chain property is why the table is self-describing and why the build needs no extra data structure.

Tracing the build on ababaca

i=1: k=0, pat[1]='b' vs pat[0]='a', no match, pi[1]=0.
i=2: k=0, 'a' == 'a', k=1, pi[2]=1.
i=3: k=1, pat[3]='b' == pat[1]='b', k=2, pi[3]=2.
i=4: k=2, pat[4]='a' == pat[2]='a', k=3, pi[4]=3.
i=5: k=3, pat[5]='c' vs pat[3]='b' - fail. Fall back k = pi[2] = 1; 'c' vs pat[1]='b' - fail. Fall back k = pi[0] = 0; 'c' vs pat[0]='a' - fail, and k is already 0 so the loop exits. pi[5]=0.
i=6: k=0, 'a' == 'a', k=1, pi[6]=1.

Position 5 is the interesting one: it took three comparisons for a single output. That is the fallback chain in action, and it is also the case the amortized argument below has to account for.

The search loop

With pi in hand, the scan over the text is a single forward pass. The text index never moves backward - there is no seek, no rewind, no buffered lookbehind.

def kmp_search(text, pat):
    if not pat:
        return
    pi = prefix_function(pat)
    m = len(pat)
    j = 0                            # how many pattern chars currently matched
    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = pi[j - 1]            # slide the pattern, not the text
        if ch == pat[j]:
            j += 1
        if j == m:
            yield i - m + 1
            j = pi[j - 1]            # continue; finds overlapping matches too

Two details are easy to get wrong. First, after a full match you must set j = pi[m-1] rather than j = 0, otherwise you miss overlapping occurrences - searching for aa in aaaa should report offsets 0, 1 and 2, and resetting to zero reports only 0 and 2. Second, the while guard is j > 0, not j >= 0; at j == 0 there is nothing left to fall back to and the character is simply consumed.

Tracing the search on abababacaba

Pattern ababaca, pi = [0,0,1,2,3,0,1]. Characters 0 through 4 (a b a b a) all match, taking j to 5. At i=5 the text has b but pat[5] is c. Instead of restarting at text offset 1, the loop sets j = pi[4] = 3, compares b against pat[3]='b', matches, and j becomes 4. One fallback, one comparison, and the text pointer never budged. The scan continues: i=6 a takes j to 5, i=7 c takes it to 6, i=8 a takes it to 7 - a full match, reported at offset 8 - 7 + 1 = 2. Then j = pi[6] = 1, and the remaining b a take j to 3 before the text runs out.

Eleven text characters, thirteen character comparisons, zero backtracking. The naive matcher on the same input re-reads the ababa prefix region four separate times.

Why it is O(n+m) - the amortized argument that actually closes

The loop body contains an unbounded while, so a per-iteration bound is not available and hand-waving about "the pattern only slides forward" is not a proof. Use a potential function.

Let the potential be j, the pattern index, which starts at 0 and is never negative. Now account for every comparison in the search loop:

• The if ch == pat[j] test runs exactly once per text character - n comparisons total, and it increases j by at most 1 each time. So j increases at most n times over the whole run.
• Each iteration of the while performs one comparison and executes j = pi[j-1]. Because pi[j-1] < j always (the border is a proper prefix), every such iteration strictly decreases j by at least 1.

A quantity that starts at 0, never drops below 0, and rises by at most n in total cannot fall more than n times in total. So the while body executes at most n times across the entire scan, not per character. Total comparisons are bounded by 2n. The reset after a match also decreases j, and there are at most n matches, which folds into the same budget.

The identical argument applied to prefix_function - where k plays the role of j and the pattern plays the role of the text - bounds the build at 2m comparisons. Hence O(n + m) time and O(m) extra space, with no dependence on the alphabet size and no adversarial input that can degrade it. That last clause is the entire selling point, and it is worth being precise about: 2n is a hard ceiling, not an average.

The equivalent framing you will see elsewhere is that the shift i - j, the text offset at which the current partial match began, never decreases. Both statements say the same thing: work is paid for by forward progress that is never refunded.

KMP as a finite automaton

The fallback loop is really an implementation detail of something cleaner. Build a DFA with m + 1 states, where state j means "the longest suffix of the text read so far that is also a prefix of the pattern has length j". State m is accepting. On each text character you take exactly one transition. There is no inner loop at all - the automaton has already resolved every fallback chain at construction time.

def build_dfa(pat, alphabet):
    pi = prefix_function(pat)
    m = len(pat)
    delta = [dict() for _ in range(m + 1)]
    for j in range(m + 1):
        for c in alphabet:
            if j < m and c == pat[j]:
                delta[j][c] = j + 1
            elif j == 0:
                delta[j][c] = 0
            else:
                delta[j][c] = delta[pi[j - 1]][c]   # copy the fallback state's row
    return delta

The construction is one pass over states, copying the row of the fallback state and overriding a single entry - the same trick that makes Aho-Corasick's goto function total.

Materializing the full transition table

The tradeoff is stark and worth doing the arithmetic on. The table has (m + 1) x |alphabet| entries. For a 1,000-character pattern over byte-valued input that is 257,000 entries; at 4 bytes each, roughly 1 MB - far past L2 on most cores, so every text character costs a scattered load into a table that will not stay resident. The pi-array version needs 4 KB, which fits comfortably in L1, and its inner loop is usually not taken at all.

The automaton wins when the alphabet is tiny. For DNA (|alphabet| = 4) a 1,000-base pattern needs 4,004 entries - about 16 KB, L1-resident, one predictable load per base and no data-dependent branch. That is a genuinely different performance profile from the fallback loop, and it is why bioinformatics tooling materializes tables that text-search tooling does not. Build cost is O(m x |alphabet|), so the table also only pays off when the same pattern is reused across many texts.

Why KMP is usually slower than the alternatives you already have

KMP's guarantee is real and its practical standing is worse than its reputation. Almost nothing that ships as a production substring search is KMP.

It inspects every text byte at least once. That is the price of never backing up, and it is also a hard floor of n character reads. Boyer-Moore and its stripped-down cousin Horspool compare right to left and, on a mismatch, jump the pattern forward by the bad character's shift - up to m positions at a time. On English text with a 20-character pattern they inspect roughly n/10 bytes. Sublinear beats linear, and no amount of constant-factor tuning closes that gap. See Boyer-Moore string matching for how those skip tables are derived.

The trivial competitor is vectorized. A memchr-accelerated naive search scans for the pattern's first byte using SIMD - a single SSE2 or AVX2 compare instruction tests 16 or 32 bytes at once - and only falls back to a byte-wise verify at the rare candidate positions. That inner loop retires bytes per cycle rather than per iteration, and on typical text the verify almost never runs past the second character. KMP's loop is one byte per iteration with a data-dependent branch that the predictor cannot learn, so it loses by a factor that is often 5x or more.

Two memory streams instead of one. KMP reads the text and randomly indexes pi. The naive loop touches only the text and a short pattern, both hot. For short patterns - and most real patterns are short - the pi build is pure overhead that the search never amortizes.

The standard-library implementations reflect this. glibc's memmem and strstr use the Two-Way algorithm, which combines a critical-factorization skip with a linear worst-case guarantee, precisely because it wants Boyer-Moore-like skipping and the worst-case bound that KMP alone provides.

Where KMP genuinely wins

Three situations, and they are narrower than textbooks imply but they are real.

Streaming input you cannot rewind. This is the strongest case. KMP's text pointer only ever moves forward, so the algorithm can consume a socket, a decompression output stream, or a tape without buffering anything beyond the current character and the O(m) table. Boyer-Moore fundamentally cannot do this: comparing right to left requires seeing m bytes at a time and jumping around inside them, which forces a sliding buffer and complicates the chunk boundary logic. If your input arrives in unpredictably sized chunks and you want a matcher whose state is a single integer j that you carry across chunk boundaries, KMP is the natural answer and the code is trivially resumable.

Adversarial input. If an attacker chooses the text, the pattern, or both, an average-case bound is not a bound. An intrusion detection system, a WAF rule engine, or a log scanner running attacker-influenced patterns over attacker-influenced traffic can be pushed into Horspool's O(nm) worst case deliberately - the skip table degenerates when the pattern's characters all appear near its end. KMP's 2n ceiling is immune. This is the same reasoning that pushes regex engines toward Thompson-style automaton simulation, covered in regex engine internals.

Small alphabets. Horspool's expected skip shrinks as the alphabet does; over a binary or 4-symbol alphabet the bad-character heuristic buys almost nothing, because every symbol occurs in the pattern. Meanwhile the DFA form of KMP becomes cheap to materialize. Binary protocol scanning and genomic search sit exactly here.

A fourth, quieter case: you wanted pi anyway. If your problem is really about borders or periodicity, the search is a free side effect.

The prefix function is worth more than the search

Practitioners meet pi as a step inside KMP and then never think about it again. It is the more useful half.

All borders, not just the longest. The complete set of border lengths of a string s of length n is the chain pi[n-1], then pi[pi[n-1]-1], and so on until you hit 0. Enumerating it costs one array walk. This is how you answer "what are all the ways this string overlaps itself", which shows up in overlap-layout-consensus assembly and in de-duplicating chunk boundaries.

Periodicity from a single number

The smallest period of s is p = n - pi[n-1], where period means s[i] == s[i+p] for every valid i. This is one of the most misquoted facts in string algorithms, because it does not mean s is a whole number of repetitions. That stronger claim holds only when n % p == 0.

• s = "abcabcabc": n = 9, pi[8] = 6, so p = 3. Since 9 % 3 == 0, the string is literally abc repeated three times.
• s = "abcabca": n = 7, pi[6] = 4, so p = 3. The period-3 relation holds at every position, but 7 % 3 == 1, so the string is not a whole repetition - it is abc twice plus a partial copy. Code that tests only p < n and concludes "periodic" will report the wrong answer here.
• s = "abcd": pi[3] = 0, so p = 4 == n - aperiodic, no non-trivial structure.

Relationship to the Z-algorithm. Z[i] is the length of the longest common prefix of s and the suffix starting at i. Z and pi carry the same information and convert to each other in O(n). Z is usually the easier tool for "how far does the prefix reach from here" problems, and its derivation is more transparent to most readers; pi is the one you need when you cannot back up, because it is computable left to right as characters arrive. Details in the Z-algorithm.

For repeated queries against a fixed text the whole framing changes - you preprocess the text once instead of the pattern, and reach for suffix arrays or suffix automata. KMP preprocesses the pattern, which is the right choice only when the text is the thing that keeps changing. If instead your pattern is a rolling window and you want expected-linear matching with cheap multi-pattern support, Rabin-Karp trades the deterministic guarantee for a rolling hash and a verification step.

Multi-pattern - Aho-Corasick as the generalization

KMP searches for one pattern. Running it k times for k patterns costs O(kn), which is exactly the wrong shape for a virus scanner, a keyword filter, or a tokenizer with thousands of literals.

Aho-Corasick is what KMP becomes when the pattern is replaced by a trie of all patterns. Each trie node has a failure link pointing to the node spelling the longest proper suffix of the current node's string that is also a prefix of some pattern - the direct generalization of pi, which is the special case where the trie is a single path. The links are computed by breadth-first traversal, so a node's failure link is resolved after its parent's, mirroring how pi[i] is computed after pi[i-1]. The result scans the text once in O(n) regardless of how many patterns there are, plus O(sum of pattern lengths) to build and O(z) to report z occurrences. Output links chain the matches that end at the same position. See Aho-Corasick.

The practical consequence: if you are reaching for KMP because you have a matching problem, check the pattern count first. One pattern over streaming or adversarial input is KMP's niche. Many patterns is Aho-Corasick. One pattern over ordinary in-memory text is almost always better served by whatever your standard library already ships.