KMP Idea: Prefix Function

KMP precomputes a longest-prefix-suffix table (pi) for the pattern. In case of a mismatch, the algorithm uses pi to jump without blindly shifting the text window by 1.

Total $O(n + m)$. The idea: use already read information.

Where used

One-time preprocessed patterns in streaming scanners and intrusion detection. A building block for understanding string automata and regex engines.

Depth

KMP remembers for each examined pattern prefix how far a meaningful comparison can continue after an error. The preprocessing specifies the lengths of suitable border structures within the pattern. This way, the text pointer does not need to be reset after a partial match.

During the search, the text index only moves forward. The pattern index can jump back using precomputed references, while already confirmed structures are retained. Both preprocessing and searching require work proportional to their input lengths.

Difficulty levels

1. Gradually determine border lengths for short patterns.
2. Continue a mismatch with the precomputed jump.
3. Justify why the text is not traversed backward multiple times.

Pitfalls

The prefix function is built for the pattern, not for the searched text. Additionally, one should not always go back to zero after an error; otherwise, the structural advantage is lost.