Knuth-Morris-Pratt

A linear-time single-pattern string search that never re-examines text characters, using a precomputed prefix-failure table.

No backtracking

The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern of length m in a text of length n in O(n + m) time. Naive matching, after a mismatch, restarts the pattern one position later and rescans; KMP instead precomputes how far it can shift the pattern using the pattern's own structure, so the text pointer never moves backward.

The failure function

The prefix function (failure table) stores, for each pattern prefix, the length of the longest proper prefix that is also a suffix of it. On a mismatch at pattern position j, the algorithm falls back to the failure value of j-1 instead of to zero, reusing the characters already known to match. Building this table is itself an O(m) self-match of the pattern.

Failure table

python

def prefix_function(p):
    m = len(p); pi = [0]*m; k = 0
    for i in range(1, m):
        while k and p[i] != p[k]:
            k = pi[k-1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

Why linear

During the scan, the pattern pointer increases on each match and only decreases via failure links; the total number of decreases is bounded by the number of increases, so the amortized work per text character is constant. This is a clean example of amortized analysis.

Relatives

• The Z-algorithm gives the same linear matching with a different (often simpler) array.
• Aho-Corasick generalizes the failure function to many patterns at once.
• The prefix function also finds the smallest period of a string and counts occurrences of borders.