Explain the KMP string matching algorithm.

Knuth-Morris-Pratt achieves O(n+m) string matching by preprocessing pattern to build failure function (LPS array) - longest proper prefix which is also suffix. During search, when mismatch occurs, use LPS to skip characters already matched instead of restarting. LPS construction is O(m), matching is O(n). Key insight: we never need to backtrack in the text, only in the pattern using precomputed information.