KMP vs naive substring search — what’s the core idea of KMP?

Answer

KMP precomputes a prefix function (LPS) so when a mismatch happens, it shifts the pattern without re-checking characters. This makes search O(n+m) instead of O(n·m).