StringsString Algorithms

Knuth–Morris–Pratt

Linear-time pattern matching that never re-reads text characters, using a precomputed failure (LPS) table of the pattern.

Learn Knuth–Morris–Pratt (KMP) →
a
a
0
b
1
c
2
a
3
b
4
y
5
lps
0
0
1
2
3
4
5
1/27Phase 1: build the LPS table for the pattern. lps[i] = length of the longest proper prefix of pattern[0..i] that is also its suffix. It tells us how far to fall back on a mismatch.
Characters being comparedPrefix that is reused after a fallbackMatchMismatch
PseudocodeLearn Knuth–Morris–Pratt (KMP) →
1lps = [0]*m; len = 0
2for i in 1 .. m-1:
3  while len > 0 and pattern[i] != pattern[len]: len = lps[len-1]
4  if pattern[i] == pattern[len]: len += 1
5  lps[i] = len
6i = j = 0
7while i < n:
8  if text[i] == pattern[j]: i += 1; j += 1
9    if j == m: report match at i-m; j = lps[j-1]
10  else if j > 0: j = lps[j-1]   # fall back, keep i
11  else: i += 1
Variables
len0
m6
Complexity
best O(n + m)
avg O(n + m)
worst O(n + m)
space O(m)
Speed