Compute the shortest string for a combination of two given strings such that the new string consist of both the strings as its subsequences.
Input : a = "pear" b = "peach" Output : pearch pearch is the shorted string such that both pear and peach are its subsequences. Input : a = "geek" b = "code" Output : gecodek
We have discussed a solution to find length of the shortest supersequence in below post.
Shortest Common Supersequence
In this post, printing of supersequence is discussed. The solution is based on below recursive approach discussed in above post as an alternate method.
Let a[0..m-1] and b[0..n-1] be two strings and m and be respective lengths. if (m == 0) return n; if (n == 0) return m; // If last characters are same, then add 1 to // result and recur for a if (a[m-1] == b[n-1]) return 1 + SCS(a, b, m-1, n-1); // Else find shortest of following two // a) Remove last character from X and recur // b) Remove last character from Y and recur else return 1 + min( SCS(a, b, m-1, n), SCS(a, b, m, n-1) );
We build a DP array to store lengths. After building the DP array, we traverse from bottom right most position. The approach of printing is similar to printing LCS.