KMP String Matching Explained for Coding Interviews: The Prefix Function Without the Pain

The Knuth-Morris-Pratt (KMP) algorithm finds a pattern in a text in O(n + m) time, guaranteed. Many candidates avoid it because it looks intimidating, but its heart is one small array, the prefix function, and once you understand that array, a whole group of string questions becomes straightforward. WHY BRUTE FORCE IS SLOW The naive approach tries every starting position and compares character by character. On inputs like text "aaaaaaaab" and pattern "aaab," it keeps re-checking the same characters, giving O(n * m). KMP avoids this by never moving backward in the text. When a mismatch happens, it uses what it already knows about the pattern to decide how far it can safely shift. THE PREFIX FUNCTION (LPS ARRAY) For each position i in the pattern, lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. For "ababc": - "a" -> 0 - "ab" -> 0 - "aba" -> 1 ("a") - "abab" -> 2 ("ab") - "ababc" -> 0 def build_lps(p): lps = [0] * len(p) k = 0 for i in range(1, len(p)): while k > 0 and p[i] != p[k]: k = lps[k - 1] if p[i] == p[k]: k += 1 lps[i] = k return lps The key line is k = lps[k - 1]: when the current extension fails, fall back to the next-shorter border instead of starting over. SEARCHING WITH LPS def kmp_search(text, p): if not p: return 0 lps, k = build_lps(p), 0 for i, ch in enumerate(text): while k > 0 and ch != p[k]: k = lps[k - 1] if ch == p[k]: k += 1 if k == len(p): return i - k + 1 # or record and set k = lps[k - 1] to find all matches return -1 WHY IT IS LINEAR Each step either advances k by one or shrinks it through fallbacks. Since k can't fall more times than it has risen, the total work is O(n) for the search and O(m) for building the table. Explaining this amortized argument briefly impresses interviewers. PROBLEMS WHERE KMP SHINES 1. Find the index of the first occurrence (strStr). The direct application. 2. Repeated substring pattern. A string s is made of a repeated block if n % (n - lps[n-1]) == 0 and lps[n-1] > 0. 3. Shortest palindrome. Build s + "#" + reverse(s), compute lps, and the last value tells you the longest palindromic prefix. Prepend the reverse of the remaining suffix. 4. Longest happy prefix (longest prefix that is also a suffix). That is exactly lps[n-1]. 5. Count occurrences, including overlapping ones, by continuing after each match with k = lps[k - 1]. KMP VERSUS OTHER OPTIONS - Rabin-Karp: simpler to code and great for multiple patterns or substring hashing, but relies on hashing with possible collisions. - Z-algorithm: also linear, and some people find it more intuitive. - Built-in find: fine in production, but interviewers asking this question usually want to see the algorithm. HOW TO PRESENT IT Start with brute force and show the repeated work on a bad input. Then introduce the idea that the pattern's own structure tells you where to resume. Build the LPS array for a short example on the whiteboard before writing code; that trace does most of the convincing. Walking through an algorithm like this under time pressure is hard. Some candidates use Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to keep their explanation structured. Once the prefix function clicks, KMP becomes one of the most reusable tools you can bring to a string problem.