KMP Algorithm
In this page:
Pattern Matching
The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern inside a text without ever moving the text pointer backward, even after a mismatch, which is what makes it faster than naive pattern matching on texts with repeated substructure.
Example: Pattern Matching
#include <iostream>
using namespace std;
int main() {
string text = "aabaabaaa", pattern = "aab";
size_t pos = text.find(pattern);
cout << "Pattern found at index " << pos << " (KMP finds this without rechecking text)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
String text = "aabaabaaa", pattern = "aab";
int pos = text.indexOf(pattern);
System.out.println("Pattern found at index " + pos + " (KMP finds this without rechecking text)");
}
}text, pattern = "aabaabaaa", "aab"
pos = text.find(pattern)
print(f"Pattern found at index {pos} (KMP finds this without rechecking text)")#include <stdio.h>
#include <string.h>
int main() {
char text[] = "aabaabaaa", pattern[] = "aab";
char *pos = strstr(text, pattern);
printf("Pattern found at index %ld (KMP finds this without rechecking text)\n", pos - text);
return 0;
}Login to try C/C++/Java code in the editor
LPS Array
The LPS (longest proper prefix that is also a suffix) array is precomputed once per pattern, and it stores, for every prefix of the pattern, how much of that prefix is also a suffix of itself, which is exactly what tells KMP how far it can safely skip on a mismatch.
Example: LPS Array
#include <iostream>
using namespace std;
int main() {
string pat = "aabaab";
int m = pat.length();
int lps[10] = {0};
int len = 0, i = 1;
while (i < m) {
if (pat[i] == pat[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
for (int j = 0; j < m; j++) cout << lps[j] << " ";
cout << endl;
return 0;
}public class Main {
public static void main(String[] args) {
String pat = "aabaab";
int m = pat.length();
int[] lps = new int[m];
int len = 0, i = 1;
while (i < m) {
if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
else if (len != 0) len = lps[len - 1];
else lps[i++] = 0;
}
for (int x : lps) System.out.print(x + " ");
}
}pat = "aabaab"
m = len(pat)
lps = [0] * m
length, i = 0, 1
while i < m:
if pat[i] == pat[length]:
length += 1; lps[i] = length; i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0; i += 1
print(lps)#include <stdio.h>
#include <string.h>
int main() {
char pat[] = "aabaab";
int m = strlen(pat), lps[10] = {0}, len = 0, i = 1;
while (i < m) {
if (pat[i] == pat[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
for (int j = 0; j < m; j++) printf("%d ", lps[j]);
printf("\n");
return 0;
}Login to try C/C++/Java code in the editor
KMP Search
During the search, KMP compares the text and pattern character by character, and the moment a mismatch happens, instead of restarting from scratch, it uses the LPS array to jump the pattern pointer forward to the next sensible position.
Example: KMP Search
#include <iostream>
using namespace std;
int main() {
string text = "abxabcabcaby", pat = "abcaby";
int n = text.size(), m = pat.size();
int lps[10] = {0};
int len = 0, i = 1;
while (i < m) {
if (pat[i] == pat[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
i = 0; int j = 0;
while (i < n) {
if (text[i] == pat[j]) { i++; j++; }
if (j == m) { cout << "Found at " << i - j << endl; break; }
else if (i < n && text[i] != pat[j]) { if (j) j = lps[j - 1]; else i++; }
}
return 0;
}public class Main {
public static void main(String[] args) {
String text = "abxabcabcaby", pat = "abcaby";
int n = text.length(), m = pat.length();
int[] lps = new int[m];
int len = 0, i = 1;
while (i < m) {
if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
else if (len != 0) len = lps[len - 1];
else lps[i++] = 0;
}
i = 0; int j = 0;
while (i < n) {
if (text.charAt(i) == pat.charAt(j)) { i++; j++; }
if (j == m) { System.out.println("Found at " + (i - j)); break; }
else if (i < n && text.charAt(i) != pat.charAt(j)) { if (j != 0) j = lps[j - 1]; else i++; }
}
}
}text, pat = "abxabcabcaby", "abcaby"
n, m = len(text), len(pat)
lps = [0] * m
length, i = 0, 1
while i < m:
if pat[i] == pat[length]:
length += 1; lps[i] = length; i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0; i += 1
i = j = 0
while i < n:
if text[i] == pat[j]:
i += 1; j += 1
if j == m:
print("Found at", i - j); break
elif i < n and text[i] != pat[j]:
j = lps[j - 1] if j else 0
if j == 0: i += 1#include <stdio.h>
#include <string.h>
int main() {
char text[] = "abxabcabcaby", pat[] = "abcaby";
int n = strlen(text), m = strlen(pat), lps[10] = {0}, len = 0, i = 1;
while (i < m) {
if (pat[i] == pat[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
i = 0; int j = 0;
while (i < n) {
if (text[i] == pat[j]) { i++; j++; }
if (j == m) { printf("Found at %d\n", i - j); break; }
else if (i < n && text[i] != pat[j]) { if (j) j = lps[j - 1]; else i++; }
}
return 0;
}Login to try C/C++/Java code in the editor
Why KMP is Fast
Because of the LPS-guided skipping, KMP runs in O(n + m) time total, where n is the text length and m is the pattern length, a big improvement over the naive approach's O(n × m) worst case on texts with lots of repetition.
Example: Why KMP is Fast
#include <iostream>
using namespace std;
int main() {
int n = 1000, m = 5;
cout << "Naive worst case: " << n * m << " comparisons" << endl;
cout << "KMP worst case: " << n + m << " comparisons" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 1000, m = 5;
System.out.println("Naive worst case: " + (n * m) + " comparisons");
System.out.println("KMP worst case: " + (n + m) + " comparisons");
}
}n, m = 1000, 5
print("Naive worst case:", n * m, "comparisons")
print("KMP worst case:", n + m, "comparisons")#include <stdio.h>
int main() {
int n = 1000, m = 5;
printf("Naive worst case: %d comparisons\n", n * m);
printf("KMP worst case: %d comparisons\n", n + m);
return 0;
}Login to try C/C++/Java code in the editor
KMP Practice
The best way to really understand KMP is to trace it by hand on a pattern with internal repetition, like aabaabaaa, and watch how the LPS array prevents it from re-checking characters it's already matched before.
Example: KMP Practice
#include <iostream>
using namespace std;
int main() {
string pat = "aabaabaaa";
int m = pat.length();
int lps[10] = {0};
int len = 0, i = 1;
while (i < m) {
if (pat[i] == pat[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
cout << "LPS for \"" << pat << "\": ";
for (int j = 0; j < m; j++) cout << lps[j] << " ";
cout << endl;
return 0;
}public class Main {
public static void main(String[] args) {
String pat = "aabaabaaa";
int m = pat.length();
int[] lps = new int[m];
int len = 0, i = 1;
while (i < m) {
if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
else if (len != 0) len = lps[len - 1];
else lps[i++] = 0;
}
System.out.print("LPS for \"" + pat + "\": ");
for (int x : lps) System.out.print(x + " ");
}
}pat = "aabaabaaa"
m = len(pat)
lps = [0] * m
length, i = 0, 1
while i < m:
if pat[i] == pat[length]:
length += 1; lps[i] = length; i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0; i += 1
print(f'LPS for "{pat}":', lps)#include <stdio.h>
#include <string.h>
int main() {
char pat[] = "aabaabaaa";
int m = strlen(pat), lps[10] = {0}, len = 0, i = 1;
while (i < m) {
if (pat[i] == pat[len]) lps[i++] = ++len;
else if (len) len = lps[len - 1];
else lps[i++] = 0;
}
printf("LPS for \"%s\": ", pat);
for (int j = 0; j < m; j++) printf("%d ", lps[j]);
printf("\n");
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: