KMP Algorithm
mediumTime: O(n + m)Space: O(m)
Signals to notice
efficient pattern matchingfailure functionno text backtracking
Brute force first
Check each position — O(nm).
The key insight
KMP: precompute failure function (longest prefix-suffix). On mismatch, jump to failure[j-1]. O(n+m).
What must stay true
Failure function tells you how far back to jump in the pattern without re-examining text characters. Text pointer never moves backward.
Easy way to go wrong
Not understanding failure function construction — it's self-matching of the pattern.