KMP Algorithm from Scratch (2026)
The Knuth-Morris-Pratt (KMP) algorithm performs pattern matching in O(n+m) time by preprocessing the pattern into a prefix function (also called failure function or pi array). It avoids redundant comparisons when a mismatch occurs.
The prefix function pi[i] stores the length of the longest proper prefix of pattern[0..i] that is also a suffix, enabling efficient skipping through the text.
Prefix Function Construction
The prefix function is built iteratively. For each position i, we compare pattern[i] with pattern[pi[i-1]] and backtrack using previously computed pi values until a match is found or we reach the start.
This construction runs in O(m) time and is the key insight that enables KMP's linear performance.
vector computePrefixFunction(string& pattern) {
int m = pattern.size();
vector pi(m, 0);
for (int i = 1; i < m; i++) {
int j = pi[i - 1];
while (j > 0 && pattern[i] != pattern[j])
j = pi[j - 1];
if (pattern[i] == pattern[j]) j++;
pi[i] = j;
}
return pi;
} KMP Pattern Matching
KMP matching scans the text character by character while tracking the current match length j in the pattern. On mismatch, j is updated to pi[j-1] instead of resetting, preserving progress in the pattern.
When j equals the pattern length, a match is found at position i - m + 1, and j is set to pi[j-1] to continue searching for overlapping matches.
vector kmpSearch(string& text, string& pattern) {
vector pi = computePrefixFunction(pattern);
vector matches;
int n = text.size(), m = pattern.size(), j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j])
j = pi[j - 1];
if (text[i] == pattern[j]) j++;
if (j == m) {
matches.push_back(i - m + 1);
j = pi[j - 1];
}
}
return matches;
} Frequently Asked Questions
What is the prefix function (pi array)?
The prefix function pi[i] stores the length of the longest proper prefix of the substring pattern[0..i] that is also a suffix. It encodes how much to shift the pattern after a mismatch.
Why is KMP O(n+m) while naive matching is O(n*m)?
KMP never backtracks in the text. Each character is compared at most once. The prefix function guarantees that the total number of while-loop iterations across the entire search is bounded by O(n+m).
Originally published on Ayodhyyya. Last updated June 1, 2026.