Mastering the Knuth-Morris-Pratt (KMP) Algorithm

String matching is one of the most foundational tasks in computer science. Whether you are typing Ctrl + F in a text editor, searching through log files on a server, querying a genomic database for DNA sequences, or scanning codebase repositories, finding a target pattern inside a body of text efficiently is crucial.

The Knuth-Morris-Pratt (KMP) algorithm, developed by Donald Knuth, James H. Morris, and Vaughan Pratt in 1977, was a breakthrough in string processing. It avoids the main bottleneck of naive searching: unnecessary backtracking over text characters that have already been matched.

💡 What You Will Learn

Why naive pattern search degrades to O(N × M) worst-case time.
How KMP achieves linear time O(N + M) by leveraging internal pattern symmetries.
How to construct and interpret the Longest Proper Prefix which is also Suffix (LPS) array.
Step-by-step interactive visualizations of LPS construction and full string search.
Clean, production-ready C++ code with edge-case handling.
15 curated practice problems ranging from beginner to competitive programming.

2. Understand the Problem

Given a Text string of length $N$ and a Pattern string of length $M$, find all starting indices in the Text where the Pattern appears completely.

Let's consider our primary example throughout this guide:

Text: ABABDABACDABABCABAB ($N = 19$)
Pattern: ABABCABAB ($M = 9$)

Using 0-based indexing, the pattern occurs starting at index 10 in the text.

Index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
Text	A	B	A	B	D	A	B	A	C	D	A	B	A	B	C	A	B	A	B
Pattern											A	B	A	B	C	A	B	A	B

When a mismatch occurs at any character during a scan, a naive search shifts the pattern right by just 1 position and restarts the comparison from the very beginning of the pattern. KMP avoids this repeated work.

3. Naive Algorithm vs. KMP

To understand KMP's brilliance, we must first analyze the drawback of the naive brute-force method.

Naive Approach

The naive search slides the pattern over the text one index at a time. For every shift, it compares characters from left to right until a mismatch occurs or the full pattern matches.

// Naive String Matching Pseudocode
function naiveSearch(text, pattern):
    N = length(text)
    M = length(pattern)
    for i from 0 to N - M:
        j = 0
        while j < M and text[i + j] == pattern[j]:
            j = j + 1
        if j == M:
            print "Match found at index " + i

Worst-case scenario: Searching for AAAAAB inside AAAAAAAAAAAAAAAB causes the naive loop to re-check almost every character $M$ times, taking $O(N \times M)$ time.

The KMP Insight

When a mismatch occurs after matching several characters, we already know what those matched characters were! KMP uses this knowledge to slide the pattern forward by more than one position and resume matching without ever moving the text pointer backwards.

// KMP Algorithm Overview Pseudocode
function KMPSearch(text, pattern):
    lps = computeLPSArray(pattern)
    i = 0  // text pointer
    j = 0  // pattern pointer
    while i < length(text):
        if pattern[j] == text[i]:
            i++, j++
        if j == length(pattern):
            reportMatch(i - j)
            j = lps[j - 1]
        else if i < length(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1] // No 'i' decrement!
            else:
                i++

Feature	Naive Algorithm	Knuth-Morris-Pratt (KMP)
Time Complexity (Worst)	$O(N \times M)$	$O(N + M)$
Time Complexity (Best)	$O(N)$	$O(N)$
Space Complexity	$O(1)$	$O(M)$ for LPS array
Text Pointer Movement	Backtracks continuously	Never moves backward

4. The Core Concept: Prefixes & Suffixes

Before constructing the LPS array, we must precisely define string prefixes, suffixes, and borders.

A Proper Prefix of a string is a prefix that is not equal to the whole string itself.
A Proper Suffix of a string is a suffix that is not equal to the whole string itself.
A Border is a substring that is both a proper prefix and a proper suffix of the same string.

Examples

Let's examine the string "ABAB":

Proper Prefixes: "", "A", "AB", "ABA"
Proper Suffixes: "", "B", "AB", "BAB"
Matching proper prefix & suffix: "AB" (length = 2)

Let's examine "AAAA":

Proper Prefixes: "A", "AA", "AAA"
Proper Suffixes: "A", "AA", "AAA"
Matching borders: "A" (len 1), "AA" (len 2), "AAA" (len 3). Longest = "AAA" (length 3).

Interactive Prefix & Suffix Visualizer

Type a string to inspect its longest proper prefix that matches a proper suffix:

5. LPS Array Explained from Scratch

LPS stands for Longest Proper Prefix which is also a Suffix. For a pattern $P$, lps[k] stores the length of the longest proper prefix of $P[0 \dots k]$ that is also a suffix of $P[0 \dots k]$.

Let's evaluate the LPS array for P = "ABABCABAB":

Index $i$	0	1	2	3	4	5	6	7	8
$P[i]$	A	B	A	B	C	A	B	A	B
Sub-string $P[0\dots i]$	A	AB	ABA	ABAB	ABABC	ABABCA	ABABCAB	ABABCABA	ABABCABAB
Longest Border	""	""	"A"	"AB"	""	"A"	"AB"	"ABA"	"ABAB"
lps[i]	0	0	1	2	0	1	2	3	4

Interactive LPS Construction Animation

Observe how len tracks the length of the previous longest prefix suffix. When a mismatch occurs (e.g., $P[i] \neq P[len]$), $len$ falls back to lps[len - 1] instead of resetting straight to 0.

Speed:

Pattern:

LPS:

Click Play or Next Step to start LPS calculation.

6. Complete KMP Search Animation

Now let's visualize how the KMP algorithm performs string searching on our main dataset.

Text: ABABDABACDABABCABAB
Pattern: ABABCABAB

Show LPS Array Show Pointers (i, j)

Speed:

Text ($i$):

Pattern ($j$):

LPS:

Ready to begin KMP search animation.

7. Additional Examples

Example A — Multiple & Overlapping Matches

Consider searching for AA in AAAAA. Notice how $j$ falls back to lps[j - 1] after a match to catch overlapping occurrences at indices 0, 1, 2, and 3.

Text:

Pattern:

Click Play to observe overlapping match handling.

Example B — No Match Found

Text: ABCDEF, Pattern: XYZ. Demonstrates graceful completion when no match exists.

Text:

Pattern:

Click Play to start.

8. Complete C++ Implementation

Here is a clean, production-grade C++ implementation suitable for technical interviews and competitive programming.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Builds the Longest Proper Prefix which is Suffix (LPS) array
vector<int> buildLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    
    if (m == 0) return lps;
    
    int len = 0; // Length of previous longest prefix suffix
    int i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                // Fallback to the previous longest prefix
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// Executes KMP string matching
// Edge case handling: Empty pattern matches at index 0.
vector<int> KMPSearch(const string& text, const string& pattern) {
    vector<int> matches;
    int n = text.length();
    int m = pattern.length();
    
    if (m == 0) {
        matches.push_back(0);
        return matches;
    }
    if (n < m) return matches;
    
    vector<int> lps = buildLPS(pattern);
    int i = 0; // Index for text
    int j = 0; // Index for pattern
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == m) {
            // Found a complete match!
            matches.push_back(i - j);
            j = lps[j - 1]; // Reset j to find overlapping matches
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return matches;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    
    vector<int> results = KMPSearch(text, pattern);
    
    cout << "Pattern found at indices: ";
    for (int idx : results) {
        cout << idx << " ";
    }
    cout << endl;
    return 0;
}

9. Common Pitfalls & Mistakes

1. Resetting len to 0 instead of lps[len - 1]

Bug: Setting len = 0 whenever $pattern[i] \neq pattern[len]$.

// INCORRECT:
if (pattern[i] != pattern[len]) {
    len = 0; // Loses partial match progress!
    i++;
}

Fix: Fall back gracefully using len = lps[len - 1] until a match is found or $len$ becomes 0.

2. Moving the Text Pointer (i) Backwards

Bug: Decrementing $i$ during a mismatch. The core invariant of KMP is that $i$ only increments.

3. Forgetting Overlapping Matches

Bug: Resetting $j = 0$ after finding a complete match. This misses overlapping pattern matches.

Fix: Set j = lps[j - 1] upon finding a match.

10. Complexity Analysis

Time Complexity: $O(N + M)$

LPS Preprocessing: $O(M)$ time. Though $len$ drops via $lps[len-1]$, $i$ increments at most $M$ times, and $len$ can increment at most $M$ times.
Matching Phase: $O(N)$ time. The text index $i$ only moves forward (max $N$ steps). The pattern pointer $j$ is decremented via $lps[j-1]$, but can never be decremented more times than it was incremented.

Space Complexity: $O(M)$

The algorithm requires an auxiliary array of size $M$ to store the LPS values. No additional space is needed for the text.

Algorithm Comparison

Algorithm	Preprocessing Time	Matching Time (Worst)	Matching Time (Average)	Extra Space
Naive Search	None	$O(N \times M)$	$O(N)$	$O(1)$
KMP	$O(M)$	$O(N)$	$O(N)$	$O(M)$
Rabin-Karp	$O(M)$	$O(N \times M)$	$O(N + M)$	$O(1)$
Boyer-Moore	$O(M + \|\Sigma\|)$	$O(N \times M)$	$O(N / M)$	$O(\|\Sigma\|)$

11. Practice Questions & Quiz

Self-Check Quiz

Q1: What is the LPS array value for index 3 of pattern "ABAB"?

A) 0

B) 1

C) 2

D) 3

Curated Practice Problems

Beginner Level

1. Compute LPS for "AAAA"

Input: "AAAA"

Output: [0, 1, 2, 3]

Explanation: For "AAAA", every proper prefix matches a suffix. Prefix "A" matches suffix "A" (len 1), "AA" matches "AA" (len 2), "AAA" matches "AAA" (len 3).

2. LeetCode 28: Find the Index of the First Occurrence in a String

Direct implementation of KMP search. Return $i - j$ on the first match.

Time: $O(N + M)$, Space: $O(M)$

Medium Level

3. LeetCode 459: Repeated Substring Pattern

Problem: Check if a string can be constructed by taking a substring of it and appending multiple copies of the substring together.

KMP Trick: Compute LPS of string $S$ length $N$. If lps[N - 1] > 0 and N % (N - lps[N - 1]) == 0, then $S$ has a repeated pattern!

Advanced Level

4. LeetCode 214: Shortest Palindrome

Problem: Convert string $S$ to a palindrome by adding characters in front of it.

KMP Trick: Create combined string $temp = S + "\#" + reverse(S)$. Build LPS array for $temp$. The last value lps.back() gives the length of the longest palindromic prefix of $S$!

12. Interview Cheat Sheet

⚡ KMP Essentials in 60 Seconds

LPS Definition: lps[i] = length of longest proper prefix of $P[0\dots i]$ that is also a suffix of $P[0\dots i]$.
Key Invariant: Text pointer $i$ never decrements.
Mismatch Rule: If $P[j] \neq T[i]$ and $j > 0$, set $j = lps[j - 1]$. If $j = 0$, increment $i$.
Match Found Rule: Record match at $i - j$, then set $j = lps[j - 1]$.
Complexities: Time $O(N + M)$, Space $O(M)$.

13. KMP Playground

Test the KMP algorithm with your custom text and pattern inputs below!

Text:

Pattern:

Comments