Strings

Knuth–Morris–Pratt

Find a pattern in text in linear time by never re-reading a character — a precomputed failure table says how far to jump.

Top row is the text; below it the pattern, aligned at the current attempt. Green is the matched prefix; blue a matching char, orange a mismatch; green text cells mark found occurrences.

What you're seeing

The naive way to search for a pattern re-aligns it one step right after every mismatch and rechecks from scratch — re-reading text characters again and again. KMP refuses to. It keeps a single text pointer that only ever moves forward; when a mismatch happens after matching a few characters, it consults a precomputed failure table to slide the pattern forward by just the right amount — reusing the characters it already matched instead of re-examining them. Watch the pattern jump ahead on a mismatch while the highlighted text position never retreats.

The rule

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

match(text, pat):
    j = 0                              # chars of pattern matched so far
    for i = 0 .. n-1:                  # i never decreases
        while j > 0 and text[i] ≠ pat[j]:
            j = failure[j-1]           # slide pattern, keep text pointer
        if text[i] == pat[j]: j += 1
        if j == m: report match; j = failure[j-1]

The invariant

The failure table encodes a reusable fact: if the first j characters of the pattern matched and then character j failed, the next possible alignment that could match must begin where the longest prefix-which-is-also-a-suffix of pat[0..j) ends — so we set j ← failure[j−1] and try again, without touching the text pointer. The consequence is the headline invariant: the text index i only ever advances, never backs up. Each step either advances i (a comparison) or decreases j (a failure jump); since j rises by at most 1 per text character, it can fall at most as many times in total — so the work is at most 2n comparisons plus the O(m) to build the table. Linear, with no re-reading.

The cost

Build tableSearch KMPO(m)O(n) Naive—O(n·m) worst

The naive scan can be quadratic — text like AAAA…AAB against pattern AAAB rechecks a long run on every shift. KMP's O(n+m) is worst-case guaranteed, never re-reading a text character. The two-letter alphabet here makes the failure jumps frequent and visible; the readout's comparison count stays comfortably under 2(n+m).

In the wild

KMP is the textbook linear-time exact matcher and a foundation of the field: it appears inside text editors and grep-family tools (alongside Boyer–Moore, which is often faster in practice by skipping ahead), in DNA/sequence search, intrusion-detection signature scanning, and streaming search where you can't rewind the input — the never-back-up property means KMP works on a one-pass stream. Its failure function is also the key to the Z-algorithm and to computing string borders and periods. Boyer–Moore and Rabin–Karp make different trade-offs (big skips; hashing), but KMP is the clean linear-worst-case guarantee.

Try this

Step through and fix your eye on the highlighted text cell — it never jumps left, even when the pattern below it leaps forward several places on a mismatch. That leap is the failure table at work: everything the pattern already matched is reused, not rechecked.

References

  1. Knuth, D. E., Morris, J. H. & Pratt, V. R. "Fast pattern matching in strings." SIAM Journal on Computing 6(2):323–350, 1977. The original.
  2. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §32.4 (The Knuth–Morris–Pratt algorithm). MIT Press, 2022.
  3. Sedgewick & Wayne. Algorithms, 4th ed., §5.3 (Substring Search). algs4.cs.princeton.edu/53substring.