KMP String Matching Algorithm Explained

Intermediate 13 min read

What you'll learn

✓Why naive string matching is O(n × m) and how KMP avoids backtracking
✓How to build the failure (partial match) table
✓The full KMP search algorithm in Python
✓Applications: pattern counting, shortest repeating unit, string period
✓When KMP beats other string matching approaches

Prerequisites

•String basics and iteration
•Understanding of prefix and suffix concepts

The Knuth-Morris-Pratt (KMP) algorithm finds all occurrences of a pattern in a text in O(n + m) time, where n is the text length and m is the pattern length. The key insight: when a mismatch happens, the pattern itself tells you where to resume — no need to re-examine characters you already matched.

Why Naive Matching Is Slow

The brute-force approach tries the pattern at every position in the text:

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            print(f"Found at index {i}")

Worst case: text = "AAAAAAAAB", pattern = "AAAAB". At each position, you match 4 characters before failing — O(n × m).

KMP avoids re-checking matched characters by precomputing how much of the pattern prefix is also a suffix of the matched portion.

The Failure Function (LPS Array)

The Longest Proper Prefix which is also Suffix (LPS) array is the heart of KMP. For each position i in the pattern, lps[i] stores the length of the longest proper prefix of pattern[0..i] that is also a suffix.

Pattern:  A  B  A  C  A  B  A  D
Index:    0  1  2  3  4  5  6  7
LPS:      0  0  1  0  1  2  3  0
At index 6 (pattern = “ABACABA”):
Prefix “ABA” = Suffix “ABA” → lps[6] = 3

LPS array for pattern ABACABAD

def build_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    return lps

print(build_lps("ABACABAD"))
# [0, 0, 1, 0, 1, 2, 3, 0]

The key line is length = lps[length - 1] — instead of resetting to zero, we fall back to the next best prefix-suffix match. This keeps the overall construction at O(m).

The KMP Search Algorithm

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    lps = build_lps(pattern)
    results = []

    i = 0  # text pointer
    j = 0  # pattern pointer

    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        
        if j == m:
            results.append(i - j)
            j = lps[j - 1]
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return results

print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
# [9]

When a mismatch occurs at pattern[j], instead of restarting from the beginning, KMP jumps j back to lps[j-1]. The text pointer i never moves backward — this guarantees O(n + m).

Applications Beyond Basic Search

Count All Occurrences

text = "AABAABAAB"
pattern = "AABAA"
matches = kmp_search(text, pattern)
print(f"Pattern occurs {len(matches)} times at positions {matches}")
# Pattern occurs 2 times at positions [0, 3]

Shortest Repeating Unit

The LPS array reveals the repeating structure of a string. If m % (m - lps[m-1]) == 0, the string is made of a repeating unit of length m - lps[m-1].

def shortest_repeating_unit(s):
    lps = build_lps(s)
    m = len(s)
    unit_len = m - lps[m - 1]
    if m % unit_len == 0:
        return s[:unit_len]
    return s

print(shortest_repeating_unit("abcabcabc"))  # "abc"
print(shortest_repeating_unit("abcdef"))      # "abcdef" (no repeat)

String Period Check

This is a common interview follow-up: “Given a string, can it be constructed by repeating a substring?”

def repeated_string_pattern(s):
    lps = build_lps(s)
    m = len(s)
    unit_len = m - lps[m - 1]
    return lps[m - 1] > 0 and m % unit_len == 0

print(repeated_string_pattern("abcabc"))  # True
print(repeated_string_pattern("abcab"))   # False

Complexity Analysis

Aspect	Value
LPS construction	O(m)
Search	O(n)
Total	O(n + m)
Space	O(m) for the LPS array

KMP vs Other Algorithms

Algorithm	Time	Preprocessing	Best For
Naive	O(nm)	None	Very short patterns
KMP	O(n+m)	O(m)	Single pattern, streaming text
Rabin-Karp	O(n+m) avg	O(m)	Multiple pattern search
Z-Algorithm	O(n+m)	O(n+m)	Similar to KMP, sometimes simpler

KMP is ideal when the text arrives as a stream — you process each character once without needing to look back.

Interview Tips

Build the LPS array first and trace through a small example — interviewers often ask you to explain it step by step.
The length = lps[length - 1] fallback is the hardest line to explain. Practice saying: “We already know pattern[0..length-1] matches, so we check the next best prefix-suffix.”
Know the repeating-unit trick — it comes up as “repeated substring pattern” (LeetCode 459).
If asked to implement from scratch, write build_lps first, test it, then write the search.
KMP is rarely needed for easy problems — if you see it in an interview, it’s a signal the problem is medium to hard.