KMP: Pattern Matching Algorithm
You'll learn how KMP uses the prefix function to skip redundant comparisons and achieve guaranteed O(n + m) time for string matching.
The Core Idea
You've already built the prefix function that tells you the longest proper prefix that's also a suffix at each position in the pattern. Now comes the payoff: using this information to search efficiently.
When a mismatch occurs during matching, instead of starting over from the beginning of the pattern, KMP "remembers" what it already matched. The prefix function tells you exactly where to resume in the pattern without rechecking characters in the text.
Think of it like reading a sentence: if you're matching "ABABAC" against text and fail at the final 'C', you don't need to go all the way back — you already know "ABABA" matched, and your prefix function tells you "ABA" repeats at the beginning, so continue from position 3 in the pattern.
The Algorithm
- Precompute the prefix function for the pattern (O(m) time)
- Scan the text with two pointers:
imoves through the textjtracks position in the pattern
- When characters match, advance both pointers
- On mismatch: use
prefix[j-1]to resetj(never backtracki!) - When
jreaches the pattern length, you found a match
The genius: i only moves forward. Each text character is examined at most once, giving O(n) for the search phase.
Total complexity: O(m) preprocessing + O(n) searching = O(n + m) guaranteed.
Why It's Powerful
Unlike naive search (O(n·m) worst case) or Rabin-Karp (expected fast, but worst-case slow), KMP guarantees linear time with no hashing tricks.
Key Takeaway: KMP achieves O(n + m) pattern matching by using the precomputed prefix function to intelligently skip redundant comparisons, never backtracking in the text.