Given a string T[1..n], a number k< n - k, T[i] = T [ i + k ] and k is smallest

Question

Given a string T[1..n], a number k< n - k, T[i] = T [ i + k ] and k is smallest such number. Give a linear time algorithm to find the period of a string.

Explanation / Answer

1. For each of the n prefixes of P, we want to know whether prefix P[1..i] is a periodic string. That is, for each i we want to know the largest k > 1 (if there is one) s.t. P[1..i] can be written as a?? for some string a. Of course, we also want to know the period. Show how to determine this for all n prefixes in linear time in the length of P. Use Z values. Case1 Z[i] is the period Case2 Z??i?? ?? i ?? Z?????? ?? i is the period 2. Given two strings of equal length A and B, describe a linear time algorithm that can determine if one of the strings is a circular rotation of the other string. Assume A = PS, B = SP, where P is the prefix string and S is the suffix string. BB = SPSP, use KMP or any linear exact match algorithm to find whether A is in BB. 3. Describe an algorithm that uses a suffix tree to compute the sp?? values used by the KMP algorithm. Hint: Match on the suffix tree From Z value, we can get sp?? value. 4. Given two input strings S1 and S2 and a parameter k, a k-cover C is a set of substrings of S1, each of length k or greater, such that S2 can be expressed as the concatenation of the substrings of S1 in some order. Note that the substrings can overlap in S1 but not in S2. Give a linear-time algorithm to find a k-cover from two strings, or to determine that no such cover exists. 1 i i+Z[i] i Z[i] Z[i] Let m(i) be the matching statistic for string S2, i.e. the length of the longest match starting at position i between S2 and a substring of S1. For simplicity I'll use m(i) to also mean the substring that matches between S2 and S1. First note that m(i + 1) >= m(i) - 1 as it is the second suffix of the string m(i). Also note that if any m(i) j, keeping track of how far in the future the value extends (i + m(i)) and find the first i that satisfies the following properties: (i) i + m(i) > j + m(j); and (ii) i - j >= k. Now switch to the interval represented by m(i) and continue as before until i + m(i) extends to the end of the string.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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