The Knuth–Morris–Pratt algorithm, commonly known as KMP, is a classic algorithm for finding a pattern inside a larger text.
Suppose we want to find:
ABAB
inside:
ABABCABAB
A naive solution tries the pattern at different positions and compares its characters from the beginning after each mismatch. The problem is that this can repeat comparisons whose results are already known.
KMP avoids this unnecessary work.
Its core idea is:
When part of the pattern has already matched, a mismatch does not mean that all information about the previous match should be discarded.
KMP preprocesses the pattern into an array called LPS, which tells us where in the pattern we can continue after a mismatch.
Why naive string searching can be inefficient
Consider:
Text: A B A B A B C
Pattern: A B A B C
The first four characters match, but then a mismatch occurs.
A naive algorithm may shift the pattern and compare several characters again even though those relationships were already discovered.
KMP uses the internal structure of the pattern to skip these redundant comparisons.
Prefix and suffix
To understand KMP, we first need the concepts of prefix and suffix.
For:
ABAB
proper prefixes include:
A
AB
ABA
Proper suffixes include:
B
AB
BAB
The longest prefix that is also a suffix is:
AB
with length 2.
This idea forms the basis of the LPS array.
What is LPS?
LPS stands for:
Longest Proper Prefix which is also a Suffix.
For every position in the pattern, it stores the length of the longest proper prefix of the current substring that is also its suffix.
Example:
Pattern: A B A B A C
Index: 0 1 2 3 4 5
LPS: 0 0 1 2 3 0
For ABA, the longest matching prefix and suffix is A, so the value is 1.
For ABAB, it is AB, so the value is 2.
For ABABA, it is ABA, so the value is 3.
Why does LPS matter?
Suppose several pattern characters have matched and then a mismatch occurs.
Instead of resetting the pattern pointer to zero, KMP uses:
j = lps[j - 1]
This preserves the part of the previous match that can still be useful.
That is the key mechanism behind KMP's efficiency.
How the search works
KMP uses two indexes:
i → text
j → pattern
If:
text[i] == pattern[j]
both indexes move forward.
If the entire pattern matches, the start position is:
i - j
If a mismatch occurs and j > 0, KMP does not move i backward. Instead:
j = lps[j - 1]
If j == 0, only i moves forward.
Building the LPS array
Pseudocode:
lps[0] = 0
length = 0
i = 1
while i < pattern.length:
if pattern[i] == pattern[length]:
length++
lps[i] = length
i++
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i++
Even LPS construction reuses information from earlier prefixes instead of restarting from scratch.
Building LPS in TypeScript
function buildLPS(pattern: string): number[] {
const lps = new Array(pattern.length).fill(0);
let length = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[length]) {
length++;
lps[i] = length;
i++;
} else if (length !== 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
return lps;
}
For:
ABABCABAB
we obtain:
[0, 0, 1, 2, 0, 1, 2, 3, 4]
Complete TypeScript implementation
function buildLPS(pattern: string): number[] {
const lps = new Array(pattern.length).fill(0);
let length = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[length]) {
length++;
lps[i] = length;
i++;
} else if (length !== 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
return lps;
}
function kmpSearch(text: string, pattern: string): number {
if (pattern.length === 0) {
return 0;
}
const lps = buildLPS(pattern);
let i = 0;
let j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
if (j === pattern.length) {
return i - j;
}
} else if (j !== 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
Example:
kmpSearch("ABABDABACDABABCABAB", "ABABCABAB");
returns:
10
Finding all occurrences
KMP can also find overlapping matches.
function kmpSearchAll(text: string, pattern: string): number[] {
if (pattern.length === 0) {
return [];
}
const lps = buildLPS(pattern);
const result: number[] = [];
let i = 0;
let j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
if (j === pattern.length) {
result.push(i - j);
j = lps[j - 1];
}
} else if (j !== 0) {
j = lps[j - 1];
} else {
i++;
}
}
return result;
}
For:
text = AAAAA
pattern = AA
it returns:
[0, 1, 2, 3]
Complexity
For text length n and pattern length m:
LPS preprocessing: O(m)
Search: O(n)
Total: O(n + m)
Space: O(m)
The text pointer never moves backward, which is one of the most important facts to understand about KMP.
KMP vs. naive search
Naive matching can take:
O(n × m)
in the worst case.
KMP guarantees:
O(n + m)
The difference becomes especially relevant for large inputs or repetitive patterns.
Consider:
Text:
AAAAAAAAAAAAAAAAAB
Pattern:
AAAAAB
A naive search repeatedly compares the same A characters. KMP uses LPS to avoid much of this duplicate work.
Real-world applications
Text search
KMP can search for patterns inside documents, files, logs, or other large text sources.
DNA sequence processing
DNA sequences can be represented as strings, making pattern-search algorithms useful for finding particular subsequences.
Log analysis
Known signatures and sequences can be searched within large log streams.
Data processing
Text-processing pipelines may repeatedly search for known token or character patterns.
Security systems
Pattern matching is relevant to systems that inspect data streams for known signatures.
KMP in technical interviews
KMP commonly appears directly or indirectly in problems involving:
- Substring search
- All pattern occurrences
- LPS construction
- Longest prefix that is also a suffix
- Repeated substring patterns
- Pattern matching in sequences
The most important part is not memorizing the implementation. It is understanding why LPS prevents unnecessary comparisons.
Why do we use lps[j - 1] after a mismatch?
If j pattern characters have already matched, then:
pattern[0 ... j-1]
matches the corresponding part of the text.
After a mismatch, we want the longest suffix of that matched region that can also serve as a prefix of the pattern.
That value is exactly:
lps[j - 1]
Instead of resetting:
j = 0
KMP preserves useful information from the previous match.
Common implementation mistake
When a mismatch occurs and j > 0, do not increment i.
Only update:
j = lps[j - 1];
The same text character must still be tested against the new pattern position.
Edge cases
Important cases include:
- Empty pattern
- Pattern longer than text
- Pattern identical to text
- Highly repetitive patterns
- Overlapping matches
Understanding repetitive patterns is especially useful because they demonstrate why LPS exists.
Should KMP always replace built-in string search?
No.
In everyday application code, built-in operations such as:
text.includes(pattern)
or:
text.indexOf(pattern)
are generally preferable.
KMP is valuable when you need to understand string matching deeply, require predictable linear-time behavior, solve algorithmic problems based on prefix/suffix relationships, or encounter it in technical interviews and competitive programming.
Conclusion
The Knuth–Morris–Pratt algorithm searches for a pattern while avoiding unnecessary repeated comparisons.
It accomplishes this by preprocessing the pattern into an LPS array.
The essential properties are:
Pattern preprocessing → LPS
Search → O(n)
Total complexity → O(n + m)
Extra space → O(m)
The key insight is simple:
A mismatch does not erase everything we learned from the characters that already matched.
The LPS array captures that information and makes KMP one of the foundational algorithms in string matching.