The KMP (Knuth-Morris-Pratt) Algorithm solves the pattern matching problem: given a text and a pattern, find all occurrences of the pattern in the text. You have probably used Ctrl+F without thinking about what happens under the hood — KMP is one way to do it.
The brute force approach is simple but slow. For each position in the text, check if the pattern matches starting there. That is O(n × m) time, which is painful for long texts and patterns. KMP does it in O(n + m) — a massive improvement.
Why Brute Force Is Slow
The problem with brute force is that it re-examines characters it has already seen. Imagine searching for "AAAB" in "AAAAAAAAAAB". At position 0, you match three A's, then fail on B. At position 1, you start over from scratch, matching three A's again. You keep redoing the same work.
KMP's insight is: when a mismatch happens, you already know some characters in the text. You can use that knowledge to skip ahead instead of backtracking. The key is precomputing how the pattern overlaps with itself.
The Failure Function (LPS Array)
The failure function, also called the Longest Proper Prefix Suffix (LPS) array, tells you for each position in the pattern, what is the longest prefix that is also a suffix. This tells KMP how far to skip when a mismatch occurs.
function buildLPS(pattern) {
const lps = new Array(pattern.length).fill(0);
let len = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[len]) {
len++;
lps[i] = len;
i++;
} else if (len !== 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
return lps;
}
console.log(buildLPS("AABAACAABAA"));
console.log(buildLPS("ABCABC"));How KMP Achieves O(n + m)
Preprocessing the pattern into the LPS array takes O(m). The search phase takes O(n) because the text pointer i never moves backward — it only advances. When a mismatch happens, the pattern pointer j jumps to lps[j-1] instead of starting over at 0.
function kmpSearch(text, pattern) {
const lps = buildLPS(pattern);
const results = [];
let i = 0, j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
}
if (j === pattern.length) {
results.push(i - j);
j = lps[j - 1];
} else if (i < text.length && text[i] !== pattern[j]) {
if (j !== 0) j = lps[j - 1];
else i++;
}
}
return results;
}
console.log(kmpSearch("AABAACAADAABAABA", "AABA"));The result is a blazing fast O(n + m) algorithm that beats brute force by a wide margin. KMP is a must-know for any serious algorithm enthusiast.