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