Problem 76: Shortest Common Supersequence
Problem Statement: Given two strings, find the shortest string that has both strings as subsequences.
Input
The first line contains string a and the second line contains string b.
Output
Print one shortest common supersequence.
Examples
Input:
abac
cab
Output:
cabac
Solution Explanation
Find the longest common subsequence (LCS) of the two strings. Then merge the two strings using the LCS to guide the interleaving so that the supersequence is minimized.
Solution in C++
#include
#include
#include
#include
using namespace std;
string shortestCommonSupersequence(string a, string b){
int n = a.size(), m = b.size();
vector> dp(n + 1, vector(m + 1, ""));
for(int i = n; i >= 0; i--) {
for(int j = m; j >= 0; j--) {
if(i == n && j == m) dp[i][j] = "";
else if(i == n) dp[i][j] = b.substr(j);
else if(j == m) dp[i][j] = a.substr(i);
else if(a[i] == b[j]) dp[i][j] = a[i] + dp[i + 1][j + 1];
else {
string s1 = a[i] + dp[i + 1][j];
string s2 = b[j] + dp[i][j + 1];
dp[i][j] = (s1.size() <= s2.size() ? s1 : s2);
}
}
}
return dp[0][0];
}
int main(){
string a, b;
cin >> a >> b;
cout << shortestCommonSupersequence(a, b) << "\n";
return 0;
}