KMP Algorithm

KMP (Knuth–Morris–Pratt) is a classic string matching algorithm used to efficiently determine whether a pattern string appears in a long text.

The core idea of KMP is:

When a mismatch occurs, instead of moving the text pointer backward, KMP uses previously matched information to quickly shift the pattern.

j = ne [ j ] ➡️ If the longest matching prefix fails, fall back to the second-longest matching prefix.

Python Template for KMP Algorithm:

# The template is based on 1-indexed array

ne = [0] * (n + 1)

# Build the prefix table {next array}
j = 0
for i in range(2, n + 1):
    while j and p[i] != p[j + 1]:
        j = ne[j]
    if p[i] == p[j + 1]:
        j += 1
    ne[i] = j

# KMP matching
j = 0
for i in range(1, m + 1):
    while j and s[i] != p[j + 1]:
        j = ne[j]
    if s[i] == p[j + 1]:
        j += 1
    if j == n:
        # find matching

Key Points: