liveBook · Manning

Knuth-Morris-Pratt algorithm

As explained in Algorithms Every Programmer Should Know

The Knuth-Morris-Pratt algorithm is a string-search procedure that uses pattern prefix-suffix information to avoid rechecking text characters after a mismatch.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through LPS construction and pointer fallback, then gives pseudocode, Python implementation, complexity, and practical tradeoffs.
Examples
Traces aabadc against aabadeaabadcaab and applies forward-only matching to live logs and network threat signatures.
What it assumes
Assumes basic strings, indexing, and Big-O; introduces proper prefixes, suffixes, and LPS through examples.
What you can do after
Build it from scratch with an LPS array and two search pointers, then assess whether preprocessing suits the pattern and workload.
How it connects
Connects longest proper prefix-suffix arrays and two-pointer scanning to brute-force string search, Rabin-Karp, and real-time streaming.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.