KMP Algorithm
mediumTime: O(n + m)Space: O(m)
Recognize the pattern
efficient pattern matchingfailure functionno text backtracking
Brute force idea
Check each position — O(nm).
Better approach
KMP: precompute failure function (longest prefix-suffix). On mismatch, jump to failure[j-1]. O(n+m).
Key invariant
Failure function tells you how far back to jump in the pattern without re-examining text characters. Text pointer never moves backward.
Watch out for
Not understanding failure function construction — it's self-matching of the pattern.