C/L/R Page 875, 34.4-1.
C/L/R Page 876, 34.4-3. You can find the matches without running any pattern matching machine. Just look at the failure function for PT. Explain how the algorithm does that. It is very simple. Please write this one as a program. Give details. Assume that the failure function has already been computed.
Let x be a string of length n. The period of x is the smallest positive integer k such that the length n-k prefix of x is the same as the length n-k suffix of x. For example, the period of string abcabcabc is 3 since the first 9-3 letters are abcabc, which are the same as the last 9-3 letters (also abcabc).
Describe an algorithm that computes the period of a length n string in time O(n).
(Hint: build the KMP pattern matching machine and examine it. Information about the period should be easy to extract from it.)