Knuth-Morris-Pratt: Prefix Function
You'll learn how KMP avoids redundant comparisons by precomputing pattern information in a special prefix function.
When searching for a pattern in text, the naive approach restarts from scratch after every mismatch. The Knuth-Morris-Pratt (KMP) algorithm does something smarter: it uses knowledge about the pattern itself to skip unnecessary comparisons.
The Core Idea
The prefix function (also called the "failure function") is an array that stores, for each position in the pattern, the length of the longest proper prefix that is also a suffix.
Translation: For every spot in your pattern, it tells you "how much of the beginning of the pattern also appears at the end, right before this spot."
Why This Matters
When you're matching and hit a mismatch, the prefix function tells you exactly where in the pattern you can safely resume matching—without rechecking characters you've already confirmed.
Analogy: Imagine you're reading "ABABC" and looking for "ABABD". When you mismatch at 'C' vs 'D', you already know the last two characters were "AB"—which matches the pattern's start! So instead of sliding all the way back, you can jump forward and continue from position 2 in the pattern.
Example
For pattern "ABABD":
- Position 0: prefix function = 0 (no prefix yet)
- Position 1: = 0 (no match: "A" vs "B")
- Position 2: = 1 ("A" matches)
- Position 3: = 2 ("AB" matches)
- Position 4: = 0 ("ABAB" has no matching prefix-suffix at 'D')
This preprocessing happens once, taking O(m) time for a pattern of length m, then enables O(n) search through text of length n.
Key Takeaway: The KMP prefix function precomputes overlap information within the pattern itself, allowing the algorithm to skip ahead intelligently after mismatches instead of rechecking already-matched characters.