Dynamic Programming: Print Shortest Common Supersequence

Problem Statement:

You are given 2 strings, you need to print shortest common supersequence.

A super sequence is a string that has both string 1 and string 2.

Example

Input:
str1 = “abac”
str2 = “cab”

Output: “cabac”

Why?

“cabac” is the shortest common supersequence where both the strings are present.

Solution

In the last question we saw how to print the length of the super sequence.

We get the LCS of 2 strings as bottom up approach, then we use the logic of printng the LCS.

The modification that we do is:

1. If the char are equal, then add it to the result string.

2. If the char are not equal, then we either move towards the left or top depending upon the value that is greater. Then add that string into the result string.

Then pust the remaining characters in to the result string.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

void print_SCS( string str1, string str2 )
{
  int m = str1.size();
  int n = str2.size();

   int L[m+1][n+1];
  
   //fill LCS in bottom up approach
   for (int i=0; i<=m; i++)
   {
     for (int j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if (str1[i-1] == str2[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
 
   //to store the result
    string ans=""; 
   
   //start from bottom right corner
   int i = m, j = n;
   while (i > 0 && j > 0)
   {
      if (str1[i-1] == str2[j-1])
      {
          ans = str1[i-1] + ans;
          i--; j--;     // reduce values of i, j and length
      }
      // compare values of L[i-1][j] and L[i][j-1] and go to greater value.
      else if (L[i-1][j] > L[i][j-1])
      {
         ans = str1[i-1] + ans;
         i--;
      }
      else
      {
         ans = str2[j-1] + ans;

         j--;
      }
   }
 
    while(i>0){
        ans = str1[i-1] + ans;
        i--;
    }
    while(j>0){
        ans = str2[j-1] + ans;
        j--;
    }
    

   cout << "SCS of " << str1 << " and " << str2 << " is " << ans<<endl;
}
 

int main()
{
    string str1 = "abac";
    string str2 = "cab";

    print_SCS(str1, str2);

  return 0;
}

Output:

SCS of abac and cab is cabac