KMP String Matching

The Knuth-Morris-Pratt algorithm finds a pattern in text in linear time by never re-examining characters, using a failure function.

Never look back

Naive substring search, on a mismatch, slides the pattern forward by one and restarts the comparison from scratch, which is O(n*m) in the worst case. The Knuth-Morris-Pratt (KMP) algorithm removes the wasted work: when a mismatch occurs after matching a prefix of the pattern, it already knows how much of that prefix is also a suffix, so it can shift the pattern to the right amount without re-examining text characters.

The failure function

KMP precomputes a failure function (or prefix function) over the pattern. For each position it records the length of the longest proper prefix of the pattern that is also a suffix ending there. On a mismatch, this table tells the algorithm which pattern position to resume from, so the text pointer only ever moves forward.

def build_failure(p):
    f = [0]*len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = f[k-1]
        if p[i] == p[k]:
            k += 1
        f[i] = k
    return f

• Preprocess the pattern: O(m)
• Search the text: O(n)
• Total: O(n + m)
• Text pointer never moves backward

Why it is linear

Each text character is compared a bounded number of times because the text pointer advances monotonically and the pattern pointer can only fall back as many times as it advanced. Summed over the scan, the total work is O(n + m). This beats the naive O(n*m) and matches the theoretical best for exact single-pattern matching.

KMP among its peers

KMP guarantees linear worst-case time and needs only O(m) extra space. The Boyer-Moore algorithm is often faster in practice by skipping ahead using the mismatched text character, and Rabin-Karp uses hashing to search for multiple patterns at once. For matching against a fixed text queried many times, a suffix tree or suffix array is preferable.