KMP Pattern Matching Algorithm

Text (Haystack)

Pattern (Needle)

Prefix Table (Pi)

Text Index (i)

Pattern Index (j)

Comparing

Status

Click "Step" or "Play" to start the visualization

Current Comparison

Match

Mismatch

Python Code - KMP Search

                pi_table = create_pi_table(needle)
            
                i, j = 0, 0
            
                while i < len(haystack) and j < len(needle):
            
                    if haystack[i] == needle[j]:
            
                        i += 1; j += 1
            
                        if j == len(needle): return i - j
            
                    else: # mismatch
            
                        if j > 0: j = pi_table[j - 1]
            
                        else: i += 1
            
                return -1

Complexity Analysis

Time Complexity O(n + m) Space Complexity O(m)

Time Complexity: O(n + m)

Breakdown

Build failure table (π-table): O(m)
Pattern matching traversal: O(n)
Text pointer never backtracks
Pattern pointer: advances ≤ n, retreats ≤ n

T(n, m) = O(m) preprocessing + O(n) matching = O(n + m)

Mathematical Intuition

Naive search is O(nm) because it restarts from position 1 after each mismatch. KMP observes that a mismatch at pattern[j] means text[i-j..i-1] matches pattern[0..j-1]. The failure function encodes: "if mismatch at j, what's the longest proper prefix of pattern[0..j-1] that's also a suffix?" This allows jumping directly to the next possible match position.

Key Insight

The text index i never decreases—guaranteeing linear time. The amortized cost of pattern index retreats is bounded by advances.

Space Complexity: O(m)

Breakdown

Failure table (π): array of m integers
Two index pointers: O(1)
No auxiliary data structures
Independent of text length n

S(m) = O(m) for failure table storage

Mathematical Intuition

The failure function π[j] stores the length of the longest proper prefix of pattern[0..j] that is also a suffix. This is a function solely of the pattern, independent of the text. Once computed, it can be reused for multiple texts without rebuilding.

Key Insight

KMP is an online algorithm: it processes the text character-by-character and can match patterns in streaming data with constant additional space per character.