Course contentsShow
← Computer Science
Lesson 835 of 2,87219. Searching and SelectionFree lesson

KMP: Pattern Matching Algorithm

Implement the KMP string matching algorithm achieving guaranteed O(n+m) time using the precomputed prefix function.

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

  1. Precompute the prefix function for the pattern (O(m) time)
  2. Scan the text with two pointers:
    • i moves through the text
    • j tracks position in the pattern
  3. When characters match, advance both pointers
  4. On mismatch: use prefix[j-1] to reset j (never backtrack i!)
  5. When j reaches 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.