Knuth-Morris-Pratt Pattern Search
Problem statement
Implement the Knuth-Morris-Pratt (KMP) algorithm to find the first occurrence of a pattern string $P[1..m]$ in a text string $S[1..n]$.
Requirements:
- Time complexity: $O(n + m)$
- Space complexity: $O(m)$ beyond the input
Constraints:
- Pattern $P$ or text $S$ may be empty
- Both may contain repeated characters
- Strings may use Unicode code points (not just ASCII)
- Inputs may be very long (millions of characters)
Part 1: Write pseudocode (or clean code) for building the prefix function (failure function) $\pi[1..m]$.
Part 2: Write pseudocode (or clean code) for the scan phase that uses $\pi$ to search $S$.
Part 3: Prove the linear time bound using an amortized argument on the number of pointer retreats.
Example
kmp_search('abc', '') -> 0Show hint
If the first $j$ characters of the pattern already matched before a mismatch, what do they tell you about where the next viable alignment could start?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.