Question 1
This question is on the linear algorithm for building suffix tree (lecture 2).
Give an example for a string S length n over final language, so that the last phase of the algorithm (expanding T n-1 to Tn) takes asymptotically as much time as possible.
Question 2
Describe efficient algorithm for the following problem
Input: a string S with length n over Σ = {1, 2, … , n}
Output: the shortest prefix T of S , so S is a prefix of T^n (concatenate T n times)
Example: for S = 12121 the output is T = 12
Question 3
Describe algorithm for the following problem with running time of O(|P| |T|):
Input: Strings P, T and a scoring function δ.
Output: a substring T’ of T so score(P, T’) is maximal, where as score(A, B) defined to be the alignment between A and B with maximum score according to the δ scoring function. (δ is a general scoring function)