3. Tired of solving the longest common subsequence problem so many times, Gabriel yearns to do...

 

Transcribed Image Text:

3. Tired of solving the longest common subsequence problem so many times, Gabriel yearns to do something different. Now, when given two strings S and T, he wants to find the shortest com- mon supersequence. That is, he wants to find a shortest (maybe not unique!) possible string SCS (S,T) (a shortest common supersequence) such that S and I are both subsequences of SCS(S, T). For example, one such shortest common supersequence of "Turing" and "Church" is "TChurcinhg". Another example is SCS("seven", "evens") = "sevens". (a) Find all SCSS for "Bob" and "Tom". (b) Find an SCS for "Apple" and "Microsoft". (c) Find all SCSs for "Homeowner" and "meow". (d) Given two strings S = 81828m of length m and T = ttt of length n as inputs, help Gabriel devise an algorithm that finds a shortest common supersequence of S and T in O(mn) time. Show that your algorithm indeed terminates in O(mn) time. 3. Tired of solving the longest common subsequence problem so many times, Gabriel yearns to do something different. Now, when given two strings S and T, he wants to find the shortest com- mon supersequence. That is, he wants to find a shortest (maybe not unique!) possible string SCS (S,T) (a shortest common supersequence) such that S and I are both subsequences of SCS(S, T). For example, one such shortest common supersequence of "Turing" and "Church" is "TChurcinhg". Another example is SCS("seven", "evens") = "sevens". (a) Find all SCSS for "Bob" and "Tom". (b) Find an SCS for "Apple" and "Microsoft". (c) Find all SCSs for "Homeowner" and "meow". (d) Given two strings S = 81828m of length m and T = ttt of length n as inputs, help Gabriel devise an algorithm that finds a shortest common supersequence of S and T in O(mn) time. Show that your algorithm indeed terminates in O(mn) time.

Answer rating: 100% (QA)

The question youve provided concerns the problem of finding the shortest common supersequence SCS of two given strings The SCS for two strings is the shortest string that has both input strings as sub... View the full answer