0

KMP Pattern Matching

Hard

The prefix table records how much of the pattern is reusable after a mismatch, so the text pointer never moves backwards.

prefix functionlinear matching
TimeO(n + m)
SpaceO(m)
Inputtext | pattern
text
a
0
b
1
a
2
b
3
c
4
a
5
b
6
c
7
a
8
b
9
a
10
b
11
a
12
b
13
d
14
pattern
a
0
b
0
a
0
b
0
d
0
phasebuilding prefix tablematchesnone yet
lps
0
0
0
0
0

Pattern "ababd". First build the prefix table, which says how far to fall back on a mismatch.

1 / 29
build lps: longest proper prefix that is also a suffix
i = 0 (text), j = 0 (pattern)
while i < n:
if text[i] == pat[j]: i++, j++
else if j > 0: j = lps[j-1] // reuse the overlap
else: i++
if j == m: match at i - m
Why it matters

Naive matching restarts the text pointer after every mismatch, which is O(n*m).

Practise this
KMP Pattern MatchingHFind the Index of the First Occurrence in a StringERepeated Substring PatternEShortest PalindromeH
Keyboard
space play← → stepr restartctrl K search
Next visualiser
Trie (Prefix Tree)