Why it matters
Naive string search is O(n × m) worst case. KMP guarantees O(n + m). For pattern matching at scale (grep, IDS, DNA search), the difference is huge.
The architecture
Failure function: for each position in the pattern, the length of the longest proper prefix that's also a suffix. Computed in O(m) with a two-pointer scan of the pattern.
Search: walk through text with a pattern pointer. On mismatch, use failure function to reset pattern pointer without moving text pointer back.
How it works end to end
Failure function computation: two pointers over pattern. For each position, extend or fall back to previous match.
Search phase: single pass over text. On character match, advance both pointers. On mismatch, consult failure function to know how far to move pattern pointer without moving text pointer back.
Alternatives: Boyer-Moore (right-to-left, skips more characters), Rabin-Karp (rolling hash, average O(n+m)), suffix automaton (indexes text for repeated queries).