Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← 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
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
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
1
2
0
0
1
2
3
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
1
2
0
0
1
2
3
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
i
a
a
a
b
0
1
2
3
j
0
1
2
0
0
1
2
3
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
i
a
a
a
b
0
1
2
3
j
0
1
2
0
0
1
2
3
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
i
a
a
a
b
0
1
2
3
j
0
1
2
0
0
1
2
3
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
i
a
a
a
b
0
1
2
3
j
0
1
2
0
0
1
2
3
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
i
a
a
a
b
0
1
2
3
j
0
1
2
0
0
1
2
3
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
i
a
a
a
b
0
1
2
3
j
0
1
2
0
0
1
2
3
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
i
a
a
a
b
0
1
2
3
0
1
2
0
0
1
2
3
algo
master
.
io
Step:
KMP Algorithm: First build the LPS (Longest Proper Prefix Suffix) array, then search.
0 / 44
Input
Repeated Pattern
Overlapping
LPS Fallback
No Match
Custom
text
=
aabxaaabxaaab
,
pattern
=
aaab
0 / 44
algo
master
.
io
Step:
KMP Algorithm: First build the LPS (Longest Proper Prefix Suffix) array, then search.
