Textbook: Gusfield, Algorithms on Strings, Trees, and Sequences do part (c) only

Question

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

Explanation / Answer

Part(c):

1. T = ababab, S = ab. Then using the algorithm derived in part(b), L will be equal to [1,3,5] because

T1 = ababab, T3 = ababab and T5 = ababab. and S is the prefix for all three of them.

|L| = 3, |S| = 2, |T| = 6 and from observation, Ti = S3 for i = 1, 3 and 5. Since |L| = 3, k = 3 and also

|L|*|S| = |T|, both equal to 6, the algorithm will return yes despite the fact that it is incorrect.

2. P = aba, T = aababa. From the algorithm is part (b), L will be found out to be [2,4], because T2 = ababaa and T4 = abaaab, and P is a prefix for both of them. |L| = 2, so k will be equal to 2. |P| = 3, and |T| = 6. Clearly, |L|*|P| = 6 = |T|. So the algorithm will return yes, which means there exist some i such that Ti = P2.

But P2 = abaaba, circular rotations of T can be given by:

T1 = aababa

T2 = ababaa

T3 = babaaa

T4 = abaaab

T5 = baaaba

T6 = aaabab

Thus there exist no i for which Ti = P2 i.e. P is not a circular match of T but the algorithm will incorrectly report yes.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.