String Matching with KMP

Opening scenario

Shortest Palindrome (LC 214). Given a string s, you may add characters only in front of it; return the shortest palindrome you can form. s = "aacecaaa" → "aaacecaaa". To solve it well you must find the longest prefix of s that is also a palindrome — which can be computed with the KMP prefix function introduced below. The classic warm-up the interviewer leads with: substring search — find the first index of needle in haystack (LC 28-style) in O(n + m).

LC numbers identify LeetCode problems.

A palindrome reads the same forward and backward. In s = "abcd", only the first character is a palindromic prefix, so prepend the reverse of "bcd" to get "dcbabcd". The questions below first explain how substring search reuses a partial match, then apply that idea to finding a palindromic prefix.

Question progression

Q1 — Why is naive substring search slow, and what is it re-checking?

Question: To find needle (length m) in haystack (length n), the textbook double loop tries every…