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.

Function Contracts

prefix_function(pattern) expects a string pattern and returns the prefix table used by KMP.

kmp_search(text, pattern) returns every starting index where pattern appears in text. For an empty pattern, this implementation returns every position from 0 through len(text).

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
 
 
def kmp_search(text, pattern):
    if pattern == "":
        return list(range(len(text) + 1))
 
    prefix = prefix_function(pattern)
    matches = []
    j = 0
 
    for i, char in enumerate(text):
        while j > 0 and char != pattern[j]:
            j = prefix[j - 1]
 
        if char == pattern[j]:
            j += 1
 
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = prefix[j - 1]
 
    return matches

The prefix table is the preprocessing step used by KMP. kmp_search returns every starting index where the pattern appears.

What the Prefix Table Means

For each position, the table records how much of the pattern can still be reused after a mismatch.

For pattern "ababaca", when a mismatch happens after matching "ababa", the matcher does not need to restart from zero. The pattern’s own prefix/suffix structure tells it where to resume.

Matching Shape

During matching, keep an index j into the pattern. When text[i] == pattern[j], advance j. When they differ, move j back using the prefix table rather than moving the text index backward.

This is the main win: the text is scanned forward only once.

For example, kmp_search("ababa", "aba") returns [0, 2]. The second match overlaps the first one, and the prefix table allows the algorithm to keep the reusable "a" after recording the first match.

Why It Works

The prefix table captures the longest pattern prefix that is also a suffix of the matched part. After a mismatch, that prefix is the only part that could still match without rechecking characters already known.

When a full match is found, the same fallback rule is used so overlapping matches are not missed.

Complexity

Building the prefix table is O(m). Matching is O(n). Total time is O(n + m), and the prefix table uses O(m) space.

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.

Another common mistake is thinking KMP skips characters in the text. It does not skip the text scan. It skips redundant pattern restarts.

When To Use It

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

Do not use KMP just to call substring search in ordinary Python code. It is mainly important when studying algorithmic string matching or when implementing exact matching under constraints.

The Main Point

KMP uses the pattern?s own prefix structure to avoid restarting from scratch after a mismatch.