· Development

The KMP failure function: where the pattern goes after a mismatch

How KMP string search picks the pattern position to compare after a mismatch: the f and next tables, how to build them, and why the search is linear, from the 1977 paper and Princeton's code.

DevelopmentAlgorithmsStrings

The simplest way to find a pattern in a text is to try every starting position in the text, compare the pattern one character at a time, and move to the next starting position on the first mismatch. Knuth, Morris and Pratt’s 1977 paper “Fast Pattern Matching in Strings” gives an example of where this gets slow: looking for aaaaaaab in aaaaaaaaaaaaaab. When the pattern is aⁿb and the text is a²ⁿb, it makes (n + 1)² character comparisons. The paper points out a second problem. Every mismatch means backing up and rereading the text, which complicates programs that read the text through a buffer.

The KMP algorithm never backs up the text. On a mismatch the text pointer stays where it is, and a table built in advance says which pattern position to compare next. This post covers what that table holds, how to build it, and why the whole search runs in linear time. It is based on that paper (SIAM Journal on Computing, vol. 6, no. 2, pp. 323–350, from a university-hosted copy), and looks at Princeton’s KMP.java from Algorithms, 4th edition, for the automaton (DFA) form. Other algorithms such as Boyer–Moore are mentioned only briefly for comparison.

Your position in the pattern already tells you what you read

Section 1 of the paper searches for the pattern abcabcacab in the text babcbabcabcaabcabcabcacabc. Say the first three pattern characters abc matched and the fourth, a, did not. Then the last four text characters read were abcx, where x is not a. You don’t need to look at the text again to know this. In the paper’s words, your position in the pattern carries enough information to recreate the characters just read.

From that alone, shifting the pattern by one, two or three places is pointless. At those positions the pattern’s first character a would have to match the text’s b, c or x, and none of them is a. So the pattern can move four places at once.

In general: if the mismatch is at the j-th pattern character, the last j − 1 text characters equal the first j − 1 pattern characters. If you know the longest stretch at the end of those j − 1 characters that can overlap the start of the pattern, you can treat that much as already matched and continue from the next character. That length depends only on the pattern, not the text, so it can be computed ahead of time.

The f table: length of the overlapping start

The paper defines this value as f[j] (indexes start at 1). f[j] is the largest i less than j such that pattern[1] … pattern[i − 1] equals pattern[j − i + 1] … pattern[j − 1]. Put plainly: among the first j − 1 pattern characters, take the longest string that is both a prefix and a suffix (not counting the whole string), and add 1 to its length. The condition holds trivially for i = 1, so f[j] ≥ 1 whenever j > 1, and by convention f[1] = 0. This post calls this table the failure function. Lectures and textbooks differ in naming and indexing, so when reading other material, first check whether it counts from 0 and whether it stores a length or a position.

On a mismatch, j becomes f[j] and the same text character is compared again with pattern[f[j]]. That is the same as sliding the pattern j − f[j] places to the right. When f[j] reaches 0, even the first pattern character doesn’t match this text character, so the whole pattern moves past it and the text moves on to its next character.

The next table: don’t go back to the same character

The table the paper actually uses for matching is next, a refinement of f. next[j] adds pattern[i] ≠ pattern[j] to the condition for f[j], and is 0 if no such i exists. The reason is simple. The mismatch happened because text character x differs from pattern[j]. If pattern[f[j]] is the same character as pattern[j], comparing x with pattern[f[j]] has a known outcome. The paper gives the relation between the two tables like this (for j > 1):

  • if pattern[j] ≠ pattern[f[j]], then next[j] = f[j]
  • if pattern[j] = pattern[f[j]], then next[j] = next[f[j]]

Here are both tables for abcabcacab, as given in the paper.

j 1 2 3 4 5 6 7 8 9 10
pattern[j] a b c a b c a c a b
f[j] 0 1 1 1 2 3 4 5 1 2
next[j] 0 1 1 0 1 1 0 5 0 1

The example in the previous section is j = 4. f[4] = 1, but pattern[4] and pattern[1] are both a, so next[4] = 0. Without a wasted comparison against pattern[1], the pattern moves past that text character, and in total it moves four places. At j = 8, pattern[8] = c and pattern[5] = b differ, so next[8] = f[8] = 5. Of the first seven characters abcabca, the final four, abca, stay matched and comparison continues at the fifth. The pattern moves 8 − 5 = 3 places.

Building the table: match the pattern against itself

Computing f[j + 1] is the same task as searching for the pattern with the pattern itself as the text. The paper pictures two copies of the pattern, one on top of the other, with the upper copy sliding right. Knowing f[j], if pattern[j] = pattern[f[j]], then f[j + 1] = f[j] + 1. If not, follow the table built so far down to a shorter overlap and repeat the same comparison. next can be computed in the same loop using the relation above, so the paper’s program never even stores the f values.

This takes O(m) time, where m is the pattern length. The paper’s argument: the variable holding the overlap length starts at 0, is increased by 1 a total of m − 1 times, and never goes negative. Each step down the table decreases it, so all of those steps together can’t exceed m − 1.

An example in Python

The code below holds the same information as the f table, adjusted for 0-based Python lists. border[i] is the length of the longest string that is both a prefix and a suffix of the first i + 1 pattern characters (not counting the whole string); in the paper’s notation that’s f[i + 2] − 1 for i from 0 to m − 2 (the last entry, border[m − 1], has no column in the paper’s f table, which stops at j = m). It uses the table corresponding to f, not the paper’s next, and finds every occurrence, not just the first. It assumes the pattern is non-empty (the paper also assumes m > 0).

def border_table(p):
    """border[i] = length of the longest proper prefix of p[:i+1] that is also its suffix"""
    border = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = border[k - 1]          # fall back to a shorter overlap
        if p[i] == p[k]:
            k += 1
        border[i] = k
    return border


def kmp_search(text, p):
    """Return every start position (0-based) where p occurs."""
    border = border_table(p)
    hits = []
    k = 0                              # number of pattern characters matched so far
    for i, c in enumerate(text):       # i only moves forward
        while k > 0 and c != p[k]:
            k = border[k - 1]
        if c == p[k]:
            k += 1
        if k == len(p):
            hits.append(i - len(p) + 1)
            k = border[k - 1]          # keep going to find overlapping occurrences
    return hits


print(border_table("abcabcacab"))                          # [0, 0, 0, 1, 2, 3, 4, 0, 1, 2]
print(kmp_search("babcbabcabcaabcabcabcacabc", "abcabcacab"))  # [15]
print(kmp_search("aaaa", "aa"))                            # [0, 1, 2]

border_table is the “match the pattern against itself” computation from the previous section, and kmp_search runs the same loop over the text. That the two functions have almost the same shape is the paper’s central point. The result [15] in the first example is where the pattern finally sits in the paper’s figure. When occurrences overlap, as in the last example, k is lowered to the border value after a match instead of being reset to 0, so overlapping occurrences are found too. Section 4 of the paper describes the same thing this way: build the next table for a pattern of length m + 1, with an imaginary character on the end that matches no text character, and after each occurrence continue matching from position next[m + 1].

Why it’s linear

The paper counts the cost of the matching phase like this. Each step either advances the text pointer by one or moves the pattern right. Neither can move more than n times (n is the text length), so once the table exists, matching takes at most 2n steps. In terms of the code above: each pass through the while loop lowers k, and k rises by at most 1 per text character, so the while loop runs at most n times in total. Adding O(m) for the table gives O(m + n) overall. The paper also stresses that the constants in these O bounds don’t depend on the alphabet size. The summary table in a 2004 Princeton lecture likewise lists KMP’s worst case as 2N character comparisons and brute force’s as MN.

Not backing up the text matters beyond time. The paper notes that when the text is read from an external file, only O(m) locations of internal memory are needed, because text already read never has to be kept.

Why use next: time spent on one character

The overall linear bound is the same with f. Section 5 of the paper says the algorithm of section 2 would still run correctly in linear time with f instead of next. The difference is how many times you can step down the table while stuck on a single text character.

The paper proves that with next, the number of consecutive times j := next[j] runs while one text character is being scanned is at most 1 + log_φ m, where φ = (1 + √5)/2 ≈ 1.618 is the golden ratio. This bound can’t be improved. Fibonacci strings (written here as s₁ = b, s₂ = a, sₙ = sₙ₋₁sₙ₋₂) are the worst case; in the paper’s example, a mismatch at j = 20 in the length-21 pattern s₈ can send j through 20, 12, 7, 4, 2, 1, 0.

With f, that theorem fails. The paper’s example is the pattern aᵐ. Since f[j] = j − 1, matching it against the text aᵐ⁻¹b… and failing at the m-th character runs j := f[j] m times and makes m − 1 redundant comparisons of the same text character before the text moves on. Computing next for the same pattern with the relation above gives next[j] = 0 for every j (this is this post’s calculation), so the whole pattern is skipped in one go. The Python code above uses the table corresponding to f, so in this case it can linger on one character, but by the previous section’s argument its total loop count still never exceeds n. next matters when input arrives in real time and the delay between characters counts.

KMP as an automaton: Princeton’s KMP.java

KMP.java on the website for Princeton’s Algorithms, 4th edition implements the same idea as a deterministic finite automaton (DFA). State j means “the first j pattern characters have matched”, and dfa[c][j] is the state after reading character c in state j. Reading the code, it is built like this:

  1. Set the restart state X to 0. Reading the first pattern character in state 0 leads to state 1.
  2. For j from 1 to m − 1, copy the mismatch entries from state X, then set only the entry for the j-th pattern character (counting from 0) to j + 1.
  3. Update X to “the state after reading that character in state X”. X is the state the automaton reaches when fed the pattern from its second character up to the current one.

Search is a single loop that runs j = dfa[c][j] once per text character and stops when j reaches m. There is no inner loop stepping down a table, so each text character always costs one table lookup. The trade-off is that the table grows with the alphabet. The file’s Javadoc says the worst-case time is proportional to n + mR and the extra space to mR, where R is the alphabet size. The constructor that takes a string fixes R = 256. The code uses each character’s value directly as an array index, so with that constructor a character whose value is 256 or more falls outside the table. What should count as one character is its own question, covered in Why character counts disagree.

Two behaviours are worth noting. search() returns only the first occurrence, and when there is none it returns the text length n rather than -1. The site’s section 5.3 page describes an improved KMPplus.java that takes time and space proportional to M + N, independent of the alphabet size. That file was not opened for this post.

Section 7 of the paper, on history, ties into this contrast. In the summer of 1969 Morris was writing a text editor for the CDC 6400 and wanted a way to avoid backing up the text file; using finite automata theory as a model, he devised a method equivalent to this algorithm. Separately, Knuth worked through Cook’s theorem as applied to Chester’s automaton and extracted the same mechanism, and Pratt modified Knuth’s data structure so that the running time no longer depended on the alphabet size. The 2004 Princeton lecture, using a binary alphabet, explains that because a match always moves to the next state, only the state to go to on a mismatch needs storing. With a larger alphabet, following next several times for the same text character stands in for one entry of the transition table.

Is it faster in practice?

The paper adds caveats here. Section 3 says the simple form from section 2 would probably not be competitive with the naive algorithm on realistic data: the naive algorithm’s worst case is m × n, but that case is unlikely in practice. With a large alphabet, partial matches are rare, and the simple form takes many unnecessary steps in the common case of failing on the pattern’s first character. The paper presents a refined version that special-cases the first character and cuts down end-of-input tests, and says this form will usually run faster than the naive algorithm. No performance measurements were made for this post. Another algorithm with a large gap between average and worst case, and how standard libraries guard against that worst case, is covered in When does quicksort hit O(n²)?

Section 8 of the same paper, a postscript added in 1976, covers the method of Boyer and Moore (and, independently, Gosper) that compares from the pattern’s last character and skips over text. With a large alphabet, it says, only about n/m text characters need to be examined on average. Searching for several patterns at once leads to a trie-based method that generalizes the next computation, and the paper notes that Aho and Corasick discovered it independently.

Things to check

  • Indexing: the paper’s f and next count from 1 and hold “the pattern position to compare next”. 0-based implementations usually hold “the overlap length”, which is off by one. In the code above, border[i] is f[i + 2] − 1 for i ≤ m − 2; the last entry, border[m − 1], has no counterpart in the paper’s f table.
  • f vs next: both give O(m + n) overall. next is what bounds the time spent on one text character to at most 1 + log_φ m steps.
  • All occurrences: after a match, lower k to the table value, not to 0, or you’ll miss overlapping occurrences.
  • DFA implementation: constant work per text character, but an m × R table. algs4’s KMP.java defaults to R = 256, finds only the first occurrence and returns n when there is none.
  • Performance: O(m + n) is a worst-case guarantee. Whether it beats naive search on typical input depends on the implementation and the data, and the paper itself says the simple form may not.

References

  • Donald E. Knuth, James H. Morris, Jr., Vaughan R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing 6(2), pp. 323–350, June 1977 (copy hosted on a Johns Hopkins University site)
  • Robert Sedgewick, Kevin Wayne, KMP.java, Algorithms, 4th edition code (file copyright notice 2002–2025)
  • Robert Sedgewick, Kevin Wayne, 5.3 Substring Search, Algorithms, 4th edition website (page marked last modified December 21, 2017)
  • Kevin Wayne, String Searching, Princeton COS 226 lecture notes, Spring 2004

All sources were checked on October 16, 2026.

Back to the blog