Question

Given two strings X and Y, a third string Z is a common superstring of X and Y if X and Y are both subsequences of 2. (Example: if X = sos and Y = soft, then Z = sosft is a common superstring of X and Y.) Design a dynamic programming algorithm which, given as input two strings X and Y, returns the length of the shortest common superstring (SCS) of X and Y. Specifically, you have to write a recurrence of X_i and Y_j, and the pseudocode. The algorithm, which has to return l(n, m), must run in time Theta(n middot m), where n = |X| and m = |Y|.

Answer 1

1) Find Longest Common Subsequence (lcs) of two given strings. For example, lcs of 'sos' and 'soft', 'so'

2) Insert non-lcs characters (in their original order in strings) to the lcs found above, and return the result. So “so” becomes “sosft” which is shortest common superstring.

Another example

str1 = “AGGTAB” and str2 = “GXTXAYB”. LCS of str1 and str2 is “GTAB”.

we insert characters of both strings in order and we get “AGXGTXAYB”

Basically we need to find a string that has both strings as subsequences and is shortest such string. If both strings have all characters different, then result is sum of lengths of two given strings. If there are common characters, then we don’t want them multiple times as the task is to minimize length. Therefore, we fist find the longest common subsequence, take one occurrence of this subsequence and add extra characters.

Length of the shortest superstring = (Sum of lengths of given two strings) - 
                                        (Length of LCS of two given strings)