KMP

KMP, or Knuth-Morris-Pratt, is a string matching algorithm that avoids restarting the pattern comparison from scratch after a mismatch.

It uses prefix information from the pattern.

Core Idea

The algorithm precomputes, for each pattern position, the length of the longest proper prefix that is also a suffix. This tells the matcher how far the pattern can shift while preserving already-known matches.

The total matching time is O(n + m) for text length n and pattern length m.

Python Example

def prefix_function(pattern):
    prefix = [0] * len(pattern)
    j = 0
 
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = prefix[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            prefix[i] = j
 
    return prefix

The prefix table is the preprocessing step used by KMP.

Common Confusions

The prefix table is about the pattern, not the text. It describes how the pattern overlaps with itself.

“Proper prefix” means the whole string is not counted as its own prefix for this purpose.

When To Use It

Use KMP when many comparisons would be repeated by naive matching and exact pattern search needs guaranteed linear time.