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

Deep dive

KMP avoids repeated comparisons by reusing information about the pattern.

Core idea:

• Precompute LPS (longest proper prefix that is also a suffix) for each prefix of the pattern.
• On mismatch at pattern index j, jump j to LPS[j-1] instead of restarting from 0.

That guarantees the text index never moves backwards, so total complexity is O(n+m).

Common pitfalls

• Off-by-one errors when building LPS.
• Handling matches: after finding a match, set j = LPS[j-1] to continue searching.
• Using KMP when a simpler approach is enough (engineering trade-off).