Knuth–Morris–Pratt (KMP) Algorithm
KMP turns information inside the pattern into a failure table. On a mismatch it preserves the longest suffix that is also a pattern prefix, avoiding comparisons the text has already proved.
The work naive matching repeats
A naive matcher restarts the pattern one position later after a mismatch. If the text and pattern contain repeated prefixes, it compares the same text characters many times and can require O(NM) work.
KMP asks what the successful prefix comparisons already imply. If pattern[0..j−1] matched and the next character fails, a suffix of that matched block may itself equal a shorter pattern prefix. Matching can resume there without moving the text index backward.
- Reuse successful comparisons
- Text index never retreats
- Worst-case linear search
Building the LPS table
LPS[i] is the length of the longest proper prefix of pattern[0..i] that is also its suffix. Proper excludes the whole substring. While constructing it, a match extends the current border; a mismatch falls back to LPS[length−1] until another border can extend or the length reaches zero.
The fallback can happen several times for one character, but each advance increases the border and each fallback decreases it. Across the whole pattern the total movement is linear, so preprocessing costs O(M).
- LPS[0] is zero
- Fallback follows borders of borders
- Construction is O(M)
Build LPS, then match without rewinding
def lps(pattern):
table = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j and pattern[i] != pattern[j]:
j = table[j - 1]
if pattern[i] == pattern[j]:
j += 1
table[i] = j
return table
def find(text, pattern):
table = lps(pattern)
j = 0
for i, c in enumerate(text):
while j and c != pattern[j]:
j = table[j - 1]
if c == pattern[j]:
j += 1
if j == len(pattern):
return i - j + 1
return -1
print("Match index:", find("ABABAC", "ABAC"))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
string t="ABABAC",p="ABAC";
vector<int>a(p.size());
for(int i=1,j=0;i<p.size();i++)
{
while(j&&p[i]!=p[j])j=a[j-1];
if(p[i]==p[j])j++;
a[i]=j;
}
for(int i=0,j=0;i<t.size();i++)
{
while(j&&t[i]!=p[j])j=a[j-1];
if(t[i]==p[j])j++;
if(j==p.size())
{
cout<<"Match index: "<<i-j+1;
break;
}
}
}class Main
{
public static void main(String[]z)
{
String t="ABABAC",p="ABAC";
int[]a=new int[p.length()];
for(int i=1,j=0;i<p.length();i++)
{
while(j>0&&p.charAt(i)!=p.charAt(j))j=a[j-1];
if(p.charAt(i)==p.charAt(j))j++;
a[i]=j;
}
for(int i=0,j=0;i<t.length();i++)
{
while(j>0&&t.charAt(i)!=p.charAt(j))j=a[j-1];
if(t.charAt(i)==p.charAt(j))j++;
if(j==p.length())
{
System.out.print("Match index: "+(i-j+1));
break;
}
}
}
}text ABABAC; pattern ABACMatch index: 2Run the example step by step
Searching with the failure function
During search, matching characters advance both i and j. A mismatch with j>0 assigns j=LPS[j−1] and retries the same text character. Only when j is zero does i advance past a mismatch. Reaching j=M reports a match at i−M.
For overlapping matches, report the position and set j=LPS[j−1] rather than resetting to zero. This preserves a suffix that may begin the next occurrence, such as pattern ABA inside ABABA.
- Retry the same text position
- Report at i−M
- Fallback after a match finds overlaps
Correctness invariant
Before every comparison, pattern[0..j−1] equals text[i−j..i−1]. LPS fallback chooses the longest smaller prefix that could still equal a suffix of that text block. Any skipped alignment would require a longer valid border, contradicting the LPS value.
Because i increases at most N times and j can fall only after earlier increases, the search is O(N). Together with preprocessing, total time is O(N+M) with O(M) auxiliary space.
- Matched prefix ends at i−1
- LPS selects the longest viable alignment
- Skipped starts cannot match
Boundaries and interview traps
An empty pattern needs an explicit API decision; many libraries return position zero. A pattern longer than the text simply produces no match. LPS values are lengths, not indexes, which prevents the common off-by-one error in j=LPS[j−1].
KMP is deterministic and collision-free, unlike rolling hash. Rabin–Karp can be simpler for many equal-length patterns, while KMP is especially strong when worst-case guarantees and exact single-pattern matching matter.
- Define empty-pattern behavior
- Lengths and indexes are different
- No hashing collisions
Trace and test the two pointer states
A useful trace separates preprocessing from searching. During LPS construction, show the pattern index, current border length, and the table after each assignment. During matching, show the text index and pattern index independently. A fallback changes only the pattern index; the same text character is compared again. Without both pointers visible, the defining advantage of KMP is hidden and a broken implementation can look convincing.
Test a pattern with no repeated prefix, one made of the same character, an overlap such as ABA in ABABA, a mismatch that falls through several borders, a full-text match, and no match. For all occurrences, resume with LPS[M−1] after reporting instead of returning. If the API accepts an empty pattern, handle it before indexing pattern[0]. These cases exercise every transition in the failure function.
A final manual check can compare KMP's reported positions with a simple matcher on randomized short strings. The simple implementation acts as an oracle while the trace confirms that the optimized matcher reaches the same answer without retreating through the text.
- Show preprocessing before search
- Fallback preserves the text index
- Overlapping matches reuse the final border