Visualize the KMP pattern matching algorithm. Watch how the LPS array enables O(N+M) string search by skipping redundant comparisons.
KMP finds all occurrences of a pattern in a text in O(N + M) time. The key insight: when a mismatch occurs, don't restart from scratch. Use the LPS (Longest Proper Prefix-Suffix) array to skip redundant comparisons.
LPS[i] = the length of the longest proper prefix of pattern[0..i] that is also a suffix. This tells us how far to "rewind" j on a mismatch without moving i.
Align pattern under text. Compare char by char. On match, advance both i and j. When j reaches pattern length, a match is found.
On a mismatch with j > 0, set j = LPS[j-1] instead of j = 0. The text pointer i never moves backward, and that is what makes KMP O(N).
When j equals the pattern length, a match is recorded at position i − j. Then j = LPS[j−1] to continue searching for overlapping matches.
KMP is the go-to for single-pattern string matching in competitive programming. The LPS array is also called the "failure function" or "partial match table". For multiple patterns, consider Aho-Corasick.