KMP: linear-time substring search with LPS
What interviewers are testing
KMP is the classic proof that string matching does not have to be quadratic, and it separates candidates who can define a prefix function from those who can actually run it. Interviewers watch whether you build the LPS table and apply the fallback j = lps[j - 1] correctly, and whether you can explain why the fallback preserves every still-possible match. It is also a calibration question: strong candidates derive the failure function instead of reciting it.
Mental model
Every time you match j characters of the pattern and then fail, the last j characters of the text already equal pattern[0..j-1]. Instead of restarting the pattern at zero and re-reading text, look at the largest proper prefix of those matched characters that is also a suffix - that is lps[j-1] - and resume from there. The text pointer i only ever moves forward, so matching costs O(n) and building the table costs O(m).
Step-by-step solution
Step 1 of 5
Naive search rechecks everything
The naive algorithm slides the pattern one position at a time and compares characters from scratch at every alignment. When a partial match fails near the end, all of that matching work is thrown away and the text pointer is rewritten to the next start position. The animation runs pattern ABABAC against ABABAABABAC. At alignment 0 the first five characters match, then C fails against A, so alignment 1 restarts from scratch and immediately fails; alignment 2 matches three characters and fails again. The text positions around the failure were already examined, but the algorithm has no memory of what they contained. In the worst case - think pattern AAAAAB over a long run of A characters - each alignment compares almost m characters, giving O(n times m) character comparisons. The animation's comparison counter makes the repeated work visible: the same text characters are tested several times across adjacent alignments.
Animation — Naive search rechecks everything
function naiveSearch(text, pattern) { for (let i = 0; i <= text.length - pattern.length; i++) { let j = 0; while (j < pattern.length && text[i + j] === pattern[j]) { j++; } if (j === pattern.length) return i; } return -1;}Variables
Alignment i = 0 matches five characters: ABABA.
Edge cases & traps
- Empty pattern: return 0 before touching lps[j - 1], or the loop indexes the pattern out of bounds; decide whether an empty needle matches at position 0.
- Pattern longer than the text: the scan ends and returns -1; never allocate or scan past text.length.
- A single-character pattern or repeated characters: proper means strictly shorter, so lps[0] is always 0 and fallback chains can be long - the amortized bound still holds.
- Patterns like AAAAAB over a long run of A characters produce deep fallback chains; they are linear in total because every fallback was paid for by an earlier match.
- Unicode text: JavaScript indexing walks UTF-16 code units, so patterns with surrogate pairs can match half a code point - iterate code points when the alphabet needs it.