Shortest Common Supersequence - GeeksforGeeks

Shortest Common Supersequence - GeeksforGeeks
Given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.

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 non-lcs 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”

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) 

// 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..m-1], Y[0..n-1] */

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..i-1]

      and Y[0..j-1] */

   for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; 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]);

     }

   }

 

   /* L[m][n] contains length of LCS for X[0..n-1] and

      Y[0..m-1] */

   return L[m][n];

}

Different approach:

// 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[i-1] == Y[j-1])

                dp[i][j] = 1 + dp[i-1][j-1];

           else

                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);

        }

    }

 

    return dp[m][n];

}

Recursive Version:O(2min(m, n))

Let X[0..m-1] and Y[0..n-1] 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[m-1] == Y[n-1]) 
     return 1 + SCS(X, Y, m-1, n-1);

  // 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, m-1, n), SCS(X, Y, m, n-1) );

int superSeq(char* X, char* Y, int m, int n)

{

    if (!m) return n;

    if (!n) return m;

 

    if (X[m-1] == Y[n-1])

        return 1 + superSeq(X, Y, m-1, n-1);

 

    return 1 + min(superSeq(X, Y, m-1, n),

                   superSeq(X, Y, m, n-1));

}

 

Extend the above program to print shortest supersequence also using function to print LCS.

Read full article from Shortest Common Supersequence - GeeksforGeeks