Compute the prefix function π for the pattern ababbabbabbababbabb when the alphabet is Σ = {a, b}.
run my program KMP.c you will get the answer.
Give an upper bound on the size of π*[q] as a function of q. Give an example to show that your bound is tight.
Since π[q] < q we trivially have |π∗[q]| <= q. This bound is tight as illustrated by the string a^q. Here π[q] = q − 1, π(1)[q] = q − 2, and so on resulting in π∗[q] = {q − 1, . . . , 0}.
Explain how to determine the occurrences of pattern P in the text T by examining the π function for the string PT (the string of length m + n that is the concatenation of P and T).
The indices in which P occurs in PT can be determined as the set M = {q | m ∈ π∗[q] and q >= 2m}.
Show how to improve KMP-MATCHER by replacing the occurrence of π in line 7 (but not line 12) by π′, where π′ is defined recursively for q = 1, 2, . . . , m by the equation
0 if π[q] = 0,
π'[q] = π'[π[q]] if π[q] != 0 and p[π[q]+1] = p[q+1]
π[q] if π[q] != 0 and p[π[q]+1] != p[q+1]Explain why the modified algorithm is correct, and explain in what sense this modification constitutes an improvement.
本质上和原算法是一样的,就是可以快速的推进,按最大的距离推进.
Give a linear-time algorithm to determine if a text T is a cyclic rotation of another string T′. For example, arc and car are cyclic rotations of each other.
Give an efficient algorithm for computing the transition function δ for the string-matching automaton corresponding to a given pattern P. Your algorithm should run in time O(m |Σ|). (Hint: Prove that δ(q, a) = δ(π[q], a) if q = m or P[q + 1] ≠ a.)
UNSOLVED
Follow @louis1992 on github to help finish this task.