Given two strings X and Y, a third string Z is a common superstring of X and Y i

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 Z. (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 relation l(i, j) = |SCS(X_i, Y_j)| that defines the length of a shortest common superstring 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|.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.