KMP Algorithm

#How does it work?

The Knuth-Morris-Pratt (KMP) algorithm fixes the naive search's habit of comparing the same letters again and again. On a mismatch it never moves back in the text; it uses the letters that already matched to slide the pattern forward.

To do so it first computes a prefix table (lps, "longest proper prefix which is also a suffix") from the pattern: lps[j] is the length of the longest part of the first j + 1 letters that is both a prefix and a suffix. For ABABCABAB the table is 0 0 1 2 0 1 2 3 4.

If a mismatch comes after j matched letters, the last lps[j − 1] of those letters already equal the start of the pattern. The pattern slides accordingly and comparing continues from there. So every letter of the text is compared at most twice.

#Try it yourself

#Step by step

1. 01Compute the pattern's prefix table (lps).
2. 02Advance through text and pattern; if the letters match, move both forward.
3. 03If the whole pattern matched, record the match and set j = lps[j − 1].
4. 04On a mismatch, if j > 0 set j = lps[j − 1]; if j = 0 move one letter forward in the text.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def prefix_table(pattern: str) -> list:
    """lps[i] = longest proper prefix of pattern[:i + 1] that is also its suffix."""
    lps = [0] * len(pattern)
    length, i = 0, 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]
        else:
            i += 1
    return lps


def kmp_search(text: str, pattern: str) -> list:
    lps = prefix_table(pattern)
    found, i, j = [], 0, 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                found.append(i - j)
                j = lps[j - 1]
        elif j > 0:
            j = lps[j - 1]  # slide the pattern; i never moves back
        else:
            i += 1
    return found


print(" ".join(map(str, prefix_table("ABABCABAB"))))
print(" ".join(map(str, kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))))

#Complexity

The text pointer never moves back, and every mismatch slides the pattern at least one place, so the total number of comparisons stays below 2n. The prefix table is built in O(m) with the same idea.

#When to use it?

Guaranteed linear search over long or repetitive text: DNA sequences, log files, pattern search over streaming data. The prefix table idea also solves problems such as finding the shortest repeating unit of a string.

#Practice

Log in to answer questions and save your progress.