The Knuth-Morris-Pratt Algorithm
The Knuth-Morris-Pratt algorithm builds a failure function for the pattern. Consider again the pattern
p=AAATA
:
Consider again searching in the text
t=AATAAAATA
:
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
A
A
T
A
A
A
A
T
A
The Knuth-Morris-Pratt algorithm always requires around
n+m
operations in the worst case where m is the length of
p
and n is the length of
t
.
