What Is KMP?
KMP (Knuth-Morris-Pratt) is a string-search algorithm that finds where a pattern appears in a long text in O(n+m). It removes the O(nm) inefficiency of naive search — which shifts one character and re-compares from scratch — by reusing information already learned from comparisons.
The one-line idea: "never rewind the text on a mismatch." Just jump the pattern by the right amount.
The Core: Failure Function (Partial-Match Table)
By analyzing the pattern itself, you precompute, for each position, the length of the longest proper prefix that is also a suffix (LPS).
On a mismatch mid-pattern, jump the pattern forward by this LPS value. It moves exactly to where the already-matched prefix can be reused, so you don't re-compare from the start.
Why Is It Faster?
Naive search backs the text pointer up one step on each mismatch and restarts. KMP never rewinds the text pointer and only moves forward — the failure function already captures what would be rewound. So the text is scanned exactly once for O(n), and computing the failure function is O(m), giving O(n+m) overall.
How It Works
Step 1. Build the failure (LPS) array from the pattern.
Step 2. Scan the text once, comparing against the pattern.
Step 3. On a match, advance both the text and pattern pointers.
Step 4. On a mismatch, jump the pattern pointer to its LPS value (keep the text pointer); if the pattern is at the start, advance only the text.
Step 5. When the whole pattern matches, that's one occurrence; jump by LPS again to find the next.
The AlgoNote visualization shows where the pattern jumps on a mismatch and that the text pointer stays put, step by step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n + m) |
| Space | O(m) |
n is the text length, m the pattern length.
Walking Through an Example
Text ABABABCA, pattern ABABC:
- •matches up to
ABAB, then mismatch atCvsA - •naive search would rewind the text and restart, but KMP reads the LPS and jumps only the pattern
- •it reuses the already-matched
AB, keeps the text pointer in place, and continues
Common Mistakes
- •Failure-function bugs: the LPS is half of KMP. Implement "longest proper prefix that is also a proper suffix" exactly.
- •Rewinding the text: backing the text pointer up degrades to O(nm) — defeating KMP's purpose.
- •Handling after a jump: if the pattern pointer is 0 and it still mismatches, advance only the text to avoid an infinite loop.
See It in Action on AlgoNote
Watch the pattern jump by the failure function on a mismatch while the text pointer never moves back, step by step on AlgoNote.