String Matching

Module 4.15 — KMP and Naive pattern matching

Preset:
Algorithm:
Speed:
Step 0 / 0

Character Comparison

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
A
B
A
B
D
A
B
A
C
D
A
B
A
B
C
A
B
A
B
A
B
A
B
C
A
B
A
B

KMP Failure Table

A
B
A
B
C
A
B
A
B
0
0
1
2
0
1
2
3
4

failure[i] = length of longest proper prefix that is also a suffix of pattern[0..i]

Stats

Comparisons0
Text length19
Pattern length9
Matches found0

Algorithm Comparison

Naive
O(n·m) worst
No preprocessing
Shift by 1
KMP
O(n+m) always
O(m) preprocess
Smart skip

KMP Key Insight

When a mismatch occurs at pattern[j], the failure table tells us the longest prefix of pattern[0..j-1] that is also a suffix. We skip to that position instead of restarting from scratch.