KMP String Search

Find a pattern in a text without ever re-reading a character of the text. A precomputed failure table says how far the pattern can jump forward after a mismatch, using the fact that part of it has already matched.

time O(n + m)

space O(m)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

lps = failure table of pattern
i = 0 (text), j = 0 (pattern)
while i < n:
  if text[i] == pattern[j]: i++, j++
  elif j > 0: j = lps[j-1]     // jump, do not rewind i
  else: i++