Shortest Common Supersequence
Given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.
Examples:
Input: str1 = "geek", str2 = "eke" Output: "geeke" Input: str1 = "AGGTAB", str2 = "GXTXAYB" Output: "AGXGTXAYB"
This problem is closely related to longest common subsequence problem. Below are steps.
1) Find Longest Common Subsequence (lcs) of two given strings. For example, lcs of “geek” and “eke” is “ek”.
2) Insert nonlcs characters (in their original order in strings) to the lcs found above, and return the result. So “ek” becomes “geeke” which is shortest common supersequence.
Let us consider another example, str1 = “AGGTAB” and str2 = “GXTXAYB”. LCS of str1 and str2 is “GTAB”. Once we find LCS, we insert characters of both strings in order and we get “AGXGTXAYB”
How does this work?
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 supersequence = (Sum of lengths of given two strings)  (Length of LCS of two given strings)
Below is the implementation of above idea. The below implementation only finds length of the shortest supersequence.
 C++

/* C program to find length of the shortest supersequence */
#include<stdio.h>
#include<string.h>
/* Utility function to get max of 2 integers */
int
max(
int
a,
int
b) {
return
(a > b)? a : b; }
/* Returns length of LCS for X[0..m1], Y[0..n1] */
int
lcs(
char
*X,
char
*Y,
int
m,
int
n);
// Function to find length of the shortest supersequence
// of X and Y.
int
shortestSuperSequence(
char
*X,
char
*Y)
{
int
m =
strlen
(X), n =
strlen
(Y);
int
l = lcs(X, Y, m, n);
// find lcs
// Result is sum of input string lengths  length of lcs
return
(m + n  l);
}
/* Returns length of LCS for X[0..m1], Y[0..n1] */
int
lcs(
char
*X,
char
*Y,
int
m,
int
n)
{
int
L[m+1][n+1];
int
i, j;
/* Following steps build L[m+1][n+1] in bottom up fashion.
Note that L[i][j] contains length of LCS of X[0..i1]
and Y[0..j1] */
for
(i=0; i<=m; i++)
{
for
(j=0; j<=n; j++)
{
if
(i == 0  j == 0)
L[i][j] = 0;
else
if
(X[i1] == Y[j1])
L[i][j] = L[i1][j1] + 1;
else
L[i][j] = max(L[i1][j], L[i][j1]);
}
}
/* L[m][n] contains length of LCS for X[0..n1] and
Y[0..m1] */
return
L[m][n];
}
/* Driver program to test above function */
int
main()
{
char
X[] =
"AGGTAB"
;
char
Y[] =
"GXTXAYB"
;
printf
(
"Length of the shortest supersequence is %d\n"
,
shortestSuperSequence(X, Y));
return
0;
}
Output:
Length of the shortest supersequence is 9
Below is Another Method to solve the above problem.
A simple analysis yields below simple recursive solution.
Let X[0..m1] and Y[0..n1] 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 X[] if (X[m1] == Y[n1]) return 1 + SCS(X, Y, m1, n1); // 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(X, Y, m1, n), SCS(X, Y, m, n1) );
Below is simple naive recursive solution based on above recursive formula.
 C++

/* A Naive recursive C++ program to find length
of the shortest supersequence */
#include<bits/stdc++.h>
using
namespace
std;
int
superSeq(
char
* X,
char
* Y,
int
m,
int
n)
{
if
(!m)
return
n;
if
(!n)
return
m;
if
(X[m1] == Y[n1])
return
1 + superSeq(X, Y, m1, n1);
return
1 + min(superSeq(X, Y, m1, n),
superSeq(X, Y, m, n1));
}
// Driver program to test above function
int
main()
{
char
X[] =
"AGGTAB"
;
char
Y[] =
"GXTXAYB"
;
cout <<
"Length of the shortest supersequence is "
<< superSeq(X, Y,
strlen
(X),
strlen
(Y));
return
0;
}
Output:
Length of the shortest supersequence is 9
Time complexity of the above solution exponential O(2^{min(m, n)}). Since there are overlapping subproblems, we can efficiently solve this recursive problem using Dynamic Programming. Below is Dynamic Programming based implementation. Time complexity of this solution is O(mn).
 C++

/* A dynamic programming based C program to find length
of the shortest supersequence */
#include<bits/stdc++.h>
using
namespace
std;
// Returns length of the shortest supersequence of X and Y
int
superSeq(
char
* X,
char
* Y,
int
m,
int
n)
{
int
dp[m+1][n+1];
// Fill table in bottom up manner
for
(
int
i = 0; i <= m; i++)
{
for
(
int
j = 0; j <= n; j++)
{
// Below steps follow above recurrence
if
(!i)
dp[i][j] = j;
else
if
(!j)
dp[i][j] = i;
else
if
(X[i1] == Y[j1])
dp[i][j] = 1 + dp[i1][j1];
else
dp[i][j] = 1 + min(dp[i1][j], dp[i][j1]);
}
}
return
dp[m][n];
}
// Driver program to test above function
int
main()
{
char
X[] =
"AGGTAB"
;
char
Y[] =
"GXTXAYB"
;
cout <<
"Length of the shortest supersequence is "
<< superSeq(X, Y,
strlen
(X),
strlen
(Y));
return
0;
}
Output:
Length of the shortest supersequence is 9
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide