Knuth-Morris-Pratt Algorithm
CS181 Fall 2020
Professor Sorin Istrail
Overview of Knuth-Morris-Pratt (KMP)
● The Knuth-Morris-Pratt (KMP) algorithm is a pattern-matching algorithm; it finds
all occurrences of a pattern P of length p in a text T of length t
● It takes advantage of the failure function f on the pattern P to search in linear
time O(p + t)!
○ The general idea is that after we’ve seen a character in T once, we should already be able to
tell whether the pattern could start there, even if we never explicitly attempted to match P1
directly to Tj
● We’ve already seen the algorithm and pseudocode for constructing the failure
function, so we’ll focus on KMP here using a similar example
Definitions
● Inputs:
○ Text T, indexed by j from 1 to t
○ Pattern P, indexed by i from 1 to p
● Output:
○ A list of positions k, where Tk : k+p = P
● Failure function, f
○ A table of p entries, where each entry f(i) is the length of the longest proper suffix of P1 : i which
is also a proper prefix of P
○ See previous slide deck for a more detailed explanation
The Algorithm
1. Calculate the failure function f for the
pattern P
2. Construct a skeleton DFA which accepts P
and includes transitions based on f
3. Initialize the skeleton DFA to state 0 and
the T pointer to 1
4. Iterate through the text T
**Here we show a version of the pseudocode which conceptualizes
KMP with an accepting skeleton DFA. In practice, the skeleton DFA
behavior can also be achieved using only the pattern P, the failure
function f, and a pointer i which indexes symbols in P rather than
states in M.
An Example
T = aabbabaabaabca
P = abaabc
aabbabaabaabca
abaabc
i 1 2 3 4 5 6
Pi a b a a b c
f(i) 0 0 1 1 2 0
**See previous set of slides for exactly how we constructed this!
aabbabaabaabca
abaabc
i 1 2 3 4 5 6
Pi a b a a b c
f(i) 0 0 1 1 2 0
a b a a b c
0 1 2 3 4 5 6
aabbabaabaabca
abaabc
i 1 2 3 4 5 6
Pi a b a a b c
f(i) 0 0 1 1 2 0
a b a a b c
0 1 2 3 4 5 6
aabbabaabaabca
abaabc
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0
j
aabbabaabaabca 8 14
abaabc
6
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
j
aabbabaabaabca
abaabc
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
j
aabbabaabaabca
ab...
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
j
aabbabaabaabca
ab...
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
j
aabbabaabaabca
ab...
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
j
aabbabaabaabca
ab...
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
j
aabbabaabaabca
ab...
i
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
aabbabaabaabca
ab...
a b a a b c
0 1 2 3 4 5 6
f(i) 0 0 1 1 2 0 8
Results:
The pattern P = “abaabc” occurs once in T = “aabbabaabaabca”
starting at position 8.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
aabbabaabaabca
abaabc