A strong answer
The simple search restarts the pattern after every mismatch, rereading text it has already matched, which costs O(n × m) on inputs such as runs of one letter. KMP keeps the text pointer moving forward only using a prefix function.
After matching k pattern characters and failing on the next, the text already read equals p[0..k−1]. The next alignment that could match is one where a prefix of the pattern lines up with a suffix of that text, which means a border of p[0..k−1]: a proper prefix that is also a suffix. The prefix function π[i] stores the longest border of p[0..i], so on a mismatch, k becomes π[k − 1] and the comparison continues with the same text character.
π is computed with the same loop on the pattern. The fallback chain π[k − 1], π[π[k − 1] − 1], and so on visits every border of the current prefix from longest to shortest, because every shorter border is a border of the longest one, so no candidate alignment is skipped.
The cost is linear by an amortized argument: k rises by at most one per character, and each fallback lowers it, so the total number of fallbacks is at most the number of characters. Building π is O(m), searching O(n), with O(m) memory. After a full match, falling back to π[m − 1] finds overlapping matches.
What the interviewer is listening for
- The definition of a border and why it gives the next safe shift.
- Why following π visits all candidates.
- The amortized O(n + m) argument.
Common mistakes
- Describing π as "the number of matching characters so far" without the border idea.
- Resetting k to 0 on mismatch, which misses matches.
- Claiming the inner while loop makes it O(n × m).