Compute Shortest Common Supersequence in C ++

In this tutorial of CodeSpeedy, we will learn about the Shortest Common Supersequence problem using C++ in a very simple way.

This is a famous interview question. We will learn to write program code in C++ in an easy way by using a simple concept. If you don’t know anything about this or how to write a program. It’s OK, you are in the right place, let’s go through it.

Firstly, What do you mean by the shortest common supersequence? Here, Two strings X and Y will be given, and we will try to find the shortest possible common sequence of these two string sequences. To do that, first of all, we will have to find all the alphabets that are common in both the strings X and Y better known as the Longest Common Subsequence. After finding the longest common subsequence, add all the remaining alphabet ( other than LCS ) of both string into the LCS without repeating any alphabet. And, your SCS is ready. Usually, SCS is not a unique string.

Given two strings string1 and string 2. NOW find the shortest common sequence that is present in both string 1 and string 2.

Examples:

Let’s see some examples-

Input:   Str 1= “ABCDEF” and Str2= “XYDEF” 

Output:  Here, the super-sequence is “ABCDEFXY”. 
         So the length of the SCS for the given strings is 8. 

Input:  Str 1= “AGGTAB” and str2= “GXTXAYB” 

Output:  Here, the super-sequence is “AGXGTXAYB”. 
         So, the length of the SCS for the given strings is 8.

Steps for writing the above program:

STEP 1: Start by finding the Longest Common Subsequence (LCS) of two given strings.

String1 = “AGGTAB” and String2 = “GXTXAYB”. Longest Common Subsequence of given str1 and str2 is “AGTB”.

STEP 2: Then insert into it those characters from the two strings that are not in the LCS.

The shortest common super-sequence of the following given string is “AGXGTXAYB”.

Program:

Now, let’s begin to write code for the shortest common supersequence problem using the above concept described –

// C++ program for the shortest supersequence 

#include<bits/stdc++.h> 
using namespace std; 
   
int max(int s1, int s2) 
{ 
    return (s1 > s2)? s1 : s2; 
} 
  

// Returns LCS
int lowestCommonSequence(char *X, char *Y, int x, int y); 
  

int shortestSuperSequence(char *X, char *Y) 
{ 
    int x = strlen(X), y = strlen(Y); 
  
    // find lcs 
    int l = lowestCommonSequence(X, Y, x, y); 
  
    //Result=sum of input string-lowestCommonSequence 
    return (x + y - l); 
} 
  

// Returns length of LCS
int lowestCommonSequence( char *X, char *Y, int x, int y) 
{ 
    int L[x + 1][y + 1]; 
    int i, j; 
  

    for (i = 0; i <= x; i++) 
    { 
        for (j = 0; j <= y; j++) 
        { 
            if (i == 0 || j == 0) 
                L[i][j] = 0; 
  
            else if (X[i - 1] == Y[j - 1]) 
                L[i][j] = L[i - 1][j - 1] + 1; 
  
            else
                L[i][j] = max(L[i - 1][j], 
                               L[i][j - 1]); 
        } 
    } 
  
    return L[x][y]; 
}


 
  
// Main function 


int main() 
{ 
    char X[] = "AGGTAB"; 
    char Y[] = "GXTXAYB"; 
      
    cout << "Length of the shortest supersequence is "
          << shortestSuperSequence(X, Y) << endl; 
          
    return 0; 
} 


Output:-

The output for the above-given program is as follow:

Length of the shortest supersequence is 8.

 

Thank you!

I hope this will help you.

Check out the solution for more problem on codespeedy-

Leave a Reply