CS141 Lab 10
For the labs of the tenth week:
-
Using an example similar to CLRS, p. 925, Fig. 32.11 to show
how to compute the prefix/failure function and how to use the function
in KMP using a diagram similar to the one (an additional page) given
in class.
-
For what kind of patterns/texts is BM faster than KMP, and when is KMP
faster than BM, assuming that the the prefix function and lookup table are
precomputed?
-
In-lab exercise: Implement the KMP algorithm given in CLRS,
p. 926, and test it on some random texts and patterns. Output the
number of (character) comparisons in each test.
TA: Provide some test data with correct numbers of comparisons.
Keep track of which students completed the exercise.
-
For keen students:
Modify the KMP search algorithm
given in class to find all the occurrences of the pattern in Theta(n)
time (don't peek at the algorithm in CLRS :-) How do you argue that your
algorithm really runs in Theta(n) time?