Textbook: Gusfield, Algorithms on Strings, Trees, and Sequences

do part (c) only:

2 LINEAR TIME STRING MATCHING Assume that you have a string matching algorithm that takes in strings S and T as inputs and returns a list of occurrences of S in T. Use this algorithm as a sub-routine to solve the following problems (a) Suppose that S is a linear string but T is a circular string, so T has no beginning or ending position. Let the ith rotation o T be T TiT[i+1) . . . T[n]TjT2] . . . TF- 11 where n = ITI. Note that T1 = T. Then S is a circular match of T if there is a rotation Ti of T such that S matches T For example, if S-raab and T = abracadabra, then T10-raabracadab, so J-10 shows that raab is a circular match of abracadabra Prove the following statement: S is a circular match of T if and only if there is rotation T, of T such that S is a prefix of Tj (b) The exact matching problem for a pattern S and circular string T is to determine if S is a circular match of T, and if so, to return a list of positionsi of T such that S is a prefix of Ti For example, if S-bla and T = babbab, then S is a prefix of T3 = bbabba and 16-bbabba, so the algorithm should return the list [3,6] You could solve the exact matching problem for S and T, and check that S matches T at position 1 for every 1 S i S T|, but this is inefficient and it requires quadratic time. Construct a linear time algorithm to solve this problem (c) Given a string S and an integer k 0, the string S* is defined by: 1, if k = 0 2. Sif k = 1, and Suppose we are interested in determining if, on input S and T, there is a rotation T, of T such that Ti = Sk for some k > 0, Consider the following algorithm 1. Use the linear-time algorithm to solve the problem from part (b) on input string S and circular text T to obtain a list L of position i of T such that S is a prefix of Ti 2. Return "Yes" if k L if |LI S T, and return "No" otherwise It turns out that this algorithm is incorrect. Create two examples 1. a string S and circular string T such that S is a circular match of T and the previous algorithm correctly reports "Yes", despite the fact that this algorithm is incorrect, and 2. a string P and circular string C such that P is not a circular match of T and the algorithm incorrectly reports "Yes". (d) Create a linear time algorithm to solve the problem posed in part (c), that is, given T and S, determine if T = Sk for some k > 0