KMP Algorithm — Knuth-Morris-Pratt String Matching Explained

KMP is one of those algorithms that every senior engineer has encountered in a 1am incident. You're processing a 500MB log file looking for a pattern — maybe a specific error signature or a token format — and your naive substr search is burning through CPU. KMP is the fix, and understanding why it works is what separates engineers who reach for the right tool versus engineers who reach for regex and hope for the best.

Published in 1977 by Knuth, Morris, and Pratt, KMP solves string pattern matching in O(n+m) time — guaranteed, not amortised, not average-case. It works by never re-examining a character in the text. Once the text pointer moves right, it never goes left. This single invariant is why the algorithm runs in linear time regardless of what adversarial pattern you throw at it. The mechanism that enforces this invariant is the LPS array — and once you truly understand LPS, you'll see it hidden inside Z-algorithm, Aho-Corasick, and even suffix arrays.

The Core Insight — The LPS Array

The LPS (Longest Proper Prefix which is also Suffix) array is where most people get lost the first time. Let me give you the mental model that actually sticks.

Every prefix of the pattern has some structure: the longest prefix of it that is also a suffix. That overlap is what LPS[i] stores.

For pattern AABAAB: - lps[0] = 0 — single char, no proper prefix - lps[1] = 1 — "AA" → prefix "A" = suffix "A" - lps[2] = 0 — "AAB" → nothing matches - lps[3] = 1 — "AABA" → prefix "A" = suffix "A" - lps[4] = 2 — "AABAA" → prefix "AA" = suffix "AA" - lps[5] = 3 — "AABAAB" → prefix "AAB" = suffix "AAB"

So lps = [0, 1, 0, 1, 2, 3]

Here is why this matters in practice: you're at text position i, pattern position j. Characters match — advance both. Mismatch at j? Instead of resetting j to 0 (naive approach — throws away all previous work), set j = lps[j-1]. You're saying: "I know the last lps[j-1] characters of what I matched still form a valid prefix — start comparing from there."

This is the O(1) reuse of previously computed information. Same idea as caching, except it's baked into the algorithm structure rather than a data store.

def build_lps(pattern: str) -> list[int]:
    m = len(pattern)
    lps = [0] * m
    length = 0  # length of previous longest prefix suffix
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # Fall back — don't increment i
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

print(build_lps('AABAAB'))   # [0, 1, 0, 1, 2, 3]
print(build_lps('ABCABD'))   # [0, 0, 0, 1, 2, 0]
print(build_lps('AABAABAAA'))# [0, 1, 0, 1, 2, 3, 4, 5, 2]

The KMP Search Algorithm

With the LPS array built, the search phase is straightforward. Two pointers i (text) and j (pattern) advance together. On a match, both advance. On a mismatch, j falls back to lps[j-1] — but i never goes backwards. This guarantees O(n) search time.

def kmp_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0:
        return []

    lps = build_lps(pattern)
    matches = []
    i = j = 0  # i = text index, j = pattern index

    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        if j == m:
            matches.append(i - j)  # match found at index i-j
            j = lps[j - 1]         # look for next match
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]     # fall back using LPS
            else:
                i += 1             # no fallback possible
    return matches

text    = 'AABAACAADAABAABA'
pattern = 'AABA'
print(kmp_search(text, pattern))  # [0, 9, 12]

Tracing Through a Mismatch

Let's trace KMP on text='AABAABAAB' and pattern='AABAAB' (lps=[0,1,0,1,2,3]):

1. i=0,j=0: A==A → match, i=1,j=1
2. i=1,j=1: A==A → match, i=2,j=2
3. i=2,j=2: B==B → match, i=3,j=3
4. i=3,j=3: A==A → match, i=4,j=4
5. i=4,j=4: A==A → match, i=5,j=5
6. i=5,j=5: B==B → match, i=6,j=6 → j==m → MATCH at index 0. j=lps[5]=3
7. i=6,j=3: A==A → match, i=7,j=4
8. i=7,j=4: A==A → match, i=8,j=5
9. i=8,j=5: B==B → match, i=9,j=6 → j==m → MATCH at index 3

Critical observation: after the first match, i did not reset to 1. It continued from 6. KMP never goes backwards in the text.

Complexity Analysis

Build LPS: O(m) time, O(m) space

Search: O(n) time — i only ever increments, and j can only decrement as many times as it has incremented. So the total number of operations is bounded by 2n.

Total: O(n+m) time, O(m) space

Comparison with naive: - Naive worst case: O(nm) — pattern 'AAAB' in text 'AAAA...A' - KMP worst case: O(n+m) — always

KMP's guarantee matters for adversarial inputs like bioinformatics (DNA sequences with lots of repetition).

Practical Applications

KMP appears in real-world systems in several forms:

Text editors: Find/replace uses Boyer-Moore-Horspool (faster in practice) but KMP is the theoretical baseline.

Bioinformatics: DNA sequence alignment — long patterns with highly repetitive alphabets (A, T, C, G) make KMP's guarantees valuable.

Network intrusion detection: Snort IDS uses Aho-Corasick (which is built on the same failure function idea as KMP) to match thousands of attack signatures simultaneously.

Python's str.find(): CPython uses a hybrid algorithm, but KMP's failure function concept underlies it.

Competitive programming: KMP appears in problems involving periodicity, string compression, and checking if one string is a rotation of another.

When you actually need to implement this yourself (not use a library): custom protocol parsers, embedded systems with no stdlib, log stream processors that need guaranteed latency, and of course — coding interviews. Knowing KMP cold without hesitation is the difference between "knows string algorithms" and "can implement them".

# Classic interview application: is s2 a rotation of s1?
def is_rotation(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    # s2 is a rotation of s1 iff s2 appears in s1+s1
    return bool(kmp_search(s1 + s1, s2))

print(is_rotation('abcde', 'cdeab'))  # True
print(is_rotation('abcde', 'abced'))  # False

# Find period of a string using LPS
def string_period(s: str) -> int:
    lps = build_lps(s)
    n = len(s)
    period = n - lps[-1]
    if n % period == 0:
        return period
    return n  # no repeated period

print(string_period('abababab'))  # 2
print(string_period('abcabc'))    # 3
print(string_period('abcdef'))    # 6 (no period)

Frequently Asked Questions