Describe a linear time algorithm that takes a string s and returns the length of the longest proper prefix of s that is also a suffix of s. Answer
Show the KMP prefix function for string ababca. Answer
How is the prefix function used in the KMP string matching algorithm? Answer
We did an amortized analysis of the time used to do n operations on a splay tree. Why was an amortized analysis sensible for that algorithm? Is there something about the algorithm that suggests an amortized analysis? Answer
Say that a step of the KMP string matching algorithm, after computing the prefix function, is to read one character of the text and do all that needs to be done for that character. The cost of handling one character c is the number of character comparisons that are made between c and a character of the pattern.
Give a banker's (or accountant's) analysis of the string matching phase of the KMP string matching algorithm. Answer