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

Kronos motion — battery never recharge

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.