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;
}