Learn
Practice
Newsletter
Resources
F
Toggle theme
0
F
Toggle theme
0
Toggle menu
← Back to All Animations
KMP (Knuth-Morris-Pratt) Algorithm
Bookmark
Input
Repeated Pattern
Overlapping
LPS Fallback
No Match
Custom
text
=
aabxaaabxaaab
,
pattern
=
aaab
text
pattern
lps[ ]
0
1
2
3
4
5
6
7
8
9
10
11
12
a
a
b
x
a
a
a
b
x
a
a
a
b
a
a
a
b
0
1
2
3
0
0
0
0
0
1
2
3
algo
master
.
io
Step:
KMP Algorithm: First build the LPS (Longest Proper Prefix Suffix) array, then search.
Variable
Value
m
4
n
13
pattern
"aaab"
Variable
Value
phase
"build_lps"
text
"aabxaaabxaaab"
undefined
-
0 / 44
Input
Repeated Pattern
Overlapping
LPS Fallback
No Match
Custom
text
=
aabxaaabxaaab
,
pattern
=
aaab
0 / 44
text
pattern
lps[ ]
0
1
2
3
4
5
6
7
8
9
10
11
12
a
a
b
x
a
a
a
b
x
a
a
a
b
a
a
a
b
0
1
2
3
0
0
0
0
0
1
2
3
algo
master
.
io
Step:
KMP Algorithm: First build the LPS (Longest Proper Prefix Suffix) array, then search.
Visualization
Variables
