KMP String Matching: Never Backtrack

Why naive search wastes work

The obvious way to find a pattern of length m inside a text of length n is to try every starting position, comparing character by character until either the whole pattern matches or a mismatch occurs. On typical text this is fast, but on adversarial or highly repetitive input it degenerates badly: searching for "AAAAB" inside a long run of "A"s matches four characters at nearly every starting position before failing on the fifth, giving O(n·m) comparisons in the worst case.

The insight: the pattern already told you something

Knuth, Morris and Pratt's 1977 algorithm notices that when a mismatch happens after matching some characters, those matched characters are a chunk of the pattern itself — you already know exactly what they are, because they matched. If part of that chunk happens to also be a prefix of the pattern, you can resume comparing from partway through the pattern instead of restarting from its first character, and — crucially — without moving the text cursor backward at all.

Building the failure function

This is precomputed once, from the pattern alone, before any text is scanned. failure[i] is the length of the longest proper prefix of the pattern that is also a proper suffix of pattern[0..i]:

buildFailure(pattern):
  failure = array of length m, failure[0] = 0
  k = 0                          // length of current matching prefix
  for i = 1 to m - 1:
    while k > 0 and pattern[i] != pattern[k]:
      k = failure[k - 1]         // fall back to a shorter prefix
    if pattern[i] == pattern[k]:
      k += 1
    failure[i] = k
  return failure

This preprocessing itself only costs O(m), using the same "never move backward" trick on the pattern compared against itself.

The search phase

With the failure function ready, scanning the text needs only one forward pass — the text index never decreases, only the pattern index jumps backward using the precomputed table:

search(text, pattern, failure):
  j = 0                                   // index into pattern
  for i = 0 to n - 1:                     // index into text, never decreases
    while j > 0 and text[i] != pattern[j]:
      j = failure[j - 1]                  // jump the pattern backward, not the text
    if text[i] == pattern[j]:
      j += 1
    if j == m:
      report match ending at i
      j = failure[j - 1]                  // continue looking for overlapping matches

Because the text index i only ever increases, each text character is examined a bounded number of times overall (an amortised argument on the pattern index gives O(n) total work for the scan), so the whole algorithm — preprocessing plus search — runs in O(n + m), with no dependence on how repetitive either string is.

Where it is used

Text search tools favour KMP or close relatives for plain substring search specifically because its worst case is guaranteed linear, unlike a naive scan which is fine on average but pathological on repetitive input — exactly the kind of input an adversary or a real genome (long runs of repeated bases) can produce. Bioinformatics tools use it to locate short motifs inside long DNA and protein sequences. Its failure-function idea also generalises directly into the Aho-Corasick algorithm, which builds a single automaton to search for many patterns simultaneously in one pass over the text.

Frequently asked questions

Try it live

Everything above runs in your browser — open KMP String Matching and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.