1. Engineering
  2. Computer Science
  3. 3 tired of solving the longest common subsequence problem so...

Question: 3 tired of solving the longest common subsequence problem so...

Question details

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 T 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 = 81s2 sm of length m and T-tit2 tn 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

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution