Due in class October 22.
You have a static string S of n characters to be preprocessed. Give an O(n) time algorithm to compute, for each k (1 ≤ k ≤ n), the longest string that occurs at least k times in S.
You have a static string S of n characters to be preprocessed. Consider a query that takes a prefix string P, and asks for the longest continuation of it that occurs at least twice in S. Give a solution that is O(n) preprocessing, and O(|P|) to answer the query.
Give an algorithm to find the longest palindrome in binary text string of length n. Use the Rabin-Karp algorithm, and dynamic programming to achieve a running time of O(n log n).
Solve the same problem using suffix trees in O(n) time. Hint: use LCA method described in class, in conjunction with a suffix tree.
In the self-adjusting trees paper [pdf] on page 683 it describes the evert operation on a link-cut tree. This operation takes a node v and makes it the root of the real tree by reversing the parent child relation for the path from v to its root. Fill in the details of how to implement evert in O(log n) time (amortized).
Some of these problems are a bit difficult. Feel free to stop by my office to discuss these problems, if necessary.