Using suffx trees give an algorithm to find a longest

Question

1. Using suffx trees, give an algorithm to find a longest common substring shared among three input strings: s₁ of length n₁, s₂ of length n₂ and s₃ of length n₃.

2. A non-empty string α is called a minimal unique substring of s if and only if it satisfies:

(i)  α occurs exactly once in s (uniqueness),

(ii) all proper prefixes of  α occur at least twice in s (mimimality), and

(iii)  α≥l for some constant l.

Give an optimal algorithm to enumerate all minimal unique substrings of s.

3. Redundant sequence identification: Given a set of k DNA sequences, S = {s_1,s_2,.......,s_k}, give an optimal algorithm to identify allsequences that are completely contained in (i.e., substrings of) at least one other sequence in S.

4. Collaborative

Let S = {s₁,s2,...........,s_k} denote a set of k genomes. The problem of fingerprinting is the task of identifying a shortest possible substring αi from each string s_i such that αi is unique to s_i -- i.e., no other genome in the set S has αi. Such an αi will be called a fingerprint of s_i.

(Note that it is OK for i to be present more than once within si.)

Give an algorithm to enumerate a fingerprint for each input genome, if one exists. Assume that no two input genomes are identical.

Attachment:- Theory_Of_Computation (1).PDF