KMP Algorithm

Preprocesses the pattern into a prefix table so a mismatch never moves the text pointer backwards — matched prefixes are reused instead of rescanned. Linear time, guaranteed.

Category: Strings
Time complexity: O(n + m)
Space complexity: O(m)

Pseudocode

build lps prefix table
scan text left to right
  match → extend
  mismatch → jump via lps
matched m chars → found

Reference implementation

# lps[i]: longest border of pat[:i+1]
while q &gt; 0 and text[i] != pat[q]:
    q = lps[q - 1]  # skip!
if text[i] == pat[q]: q += 1
if q == m: return i - m + 1

Open the interactive KMP Algorithm visualisation →