Imagine searching a long run of A’s for AAAAAB. A simple search may match five characters, hit a mismatch, then revisit text it has already checked. The Knuth-Morris-Pratt (KMP) algorithm uses what the partial match revealed: some of those characters may already match the beginning of the pattern. section 5.0 section 5.4
KMP first builds an LPS (longest prefix that is also a suffix) array for the pattern. At each position, it records the length of the longest proper prefix that also ends there. “Proper” means the prefix is shorter than the portion being examined. For XYZXY, XY is both a proper prefix and a suffix, so its length is 2. section 5.1 section 5.1.1
Table 5.1 Step-by-Step LPS array construction for "aabadc"
|
Index (i)
|
Current char (pattern[i])
|
Current prefix (length)
|
Compare against (pattern[length])
|
Match/Mismatch Action
|
LPS array
|
|
0
|
a
|
0
|
N/A (Base case)
|
lps[0] = 0.
|
[0, 0, 0, 0, 0, 0]
|
|
1
|
a
|
0
|
pattern[0]=('a')
|
Match. Increment length to 1. Record lps[1] = 1.
|
[0, 1, 0, 0, 0, 0]
|
|
2
|
b
|
1
|
pattern[1]=('a')
|
Mismatch. Fallback to length becomes lps[0] Compare again 'b' vs pattern[0] ('a'). Mismatch. Record lps[2] = 0. |
[0, 1, 0, 0, 0, 0]
|
|
3
|
a
|
0
|
pattern[0]=('a')
|
Match. Increment length to 1. Record lps[3] = 1.
|
[0, 1, 0, 1, 0, 0]
|
|
4
|
d
|
1
|
pattern[1]=('a')
|
Mismatch. Fallback to length becomes lps[0]. Compare again: 'd' vs pattern[0] ('a'). Mismatch. Record lps[4] = 0.
|
[0, 1, 0, 1, 0, 0]
|
|
5
|
c
|
0
|
pattern[0]=('a')
|
Mismatch. No fallback possible (length is already 0). Record lps[5] = 0.
|
[0, 1, 0, 1, 0, 0]
|
Follow the table to build LPS for aabadc. It shows both a direct match and a mismatch that falls back to a shorter candidate prefix; the finished array is [0, 1, 0, 1, 0, 0]. section 5.1.1
Once LPS is ready, search with a text pointer i and a pattern pointer j:
- When the characters match, advance both pointers. When the whole pattern matches, record its starting position and use LPS to resume searching. section 5.1.1
- On a mismatch after j matched characters, set j to LPS[j − 1] and compare the current text character again. If j is already zero, advance i instead. The text pointer never moves backward. section 5.1.1 section 5.4
A mismatch without starting over
Search aabadeaabadcaab for aabadc. The first five characters match, but the next text character, e, does not match c. Here LPS[4] is 0, so j returns to 0 while i stays on e. After e fails against the pattern’s first character, i advances; the full pattern begins at index 6. section 5.1 section 5.1.1
For a pattern of length m and text of length n, building LPS takes O(m) time and scanning takes O(n), for O(n + m) total time and an auxiliary array of length m. That forward-only scan suits live logs and incoming network traffic, where previously seen data may no longer be available. Preprocessing has a cost, though: for a pattern with no useful repeated prefix, a simpler search may be preferable in practice, even though KMP retains its linear-time guarantee. section 5.1.1 section 5.2.1 section 5.2.2 section 5.3.2
