Knuth-Morris-Pratt Pattern Search

Reported in interviews at Citadel Two Sigma

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', '') -> 0
Show 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.

Related free problems