Example exercise. Compute the prefix function pi for the pattern abaabab and show the comparisons made by the KMP algorithm on the pattern and text abababaabaabbababaabab.
Prefix Function
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
P[i] |
a |
b |
a |
a |
b |
a |
b |
D[i] |
0 |
0 |
1 |
1 |
2 |
3 |
2 |
Comparisons made in KMP
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
T |
a |
b |
a |
b |
a |
b |
a |
a |
b |
a |
a |
b |
b |
a |
b |
a |
b |
a |
a |
b |
a |
b |
|
1 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
a |
b |
a |
a |
b |
a |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
6 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
a |
a |
b |
a |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
9 |
10 |
11 |
12 |
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
a |
a |
b |
a |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
15 |
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
a |
a |
b |
a |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
a |
a |
b |
a |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
a |
a |
b |
a |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
20 |
21 |
22 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
a |
a |
b |
a |
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23 |
24 |
25 |
26 |
27 |
28 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
a |
a |
b |
a |
b |
Total: 28 comparisons