Printing Shortest Common Supersequence | A dynamic programming based C ++ program print shortest supersequence of two strings ; returns shortest supersequence of X and Y ; dp [ i ] [ j ] contains length of shortest supersequence for X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; Fill table in bottom up manner ; Below steps follow recurrence relation ; string to store the shortest supersequence ; Start from the bottom right corner and one by one push characters in output string ; If current character in X and Y are same , then current character is part of shortest supersequence ; Put current character in result ; reduce values of i , j and index ; If current character in X and Y are different ; Put current character of Y in result ; reduce values of j and index ; Put current character of X in result ; reduce values of i and index ; If Y reaches its end , put remaining characters of X in the result string ; If X reaches its end , put remaining characters of Y in the result string ; reverse the string and return it ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; string printShortestSuperSeq ( string X , string Y ) { int m = X . length ( ) ; int n = Y . length ( ) ; int dp [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 ) dp [ i ] [ j ] = j ; else if ( j == 0 ) 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 ] ) ; } } string str ; int i = m , j = n ; while ( i > 0 && j > 0 ) { if ( X [ i - 1 ] == Y [ j - 1 ] ) { str . push_back ( X [ i - 1 ] ) ; i -- , j -- ; } else if ( dp [ i - 1 ] [ j ] > dp [ i ] [ j - 1 ] ) { str . push_back ( Y [ j - 1 ] ) ; j -- ; } else { str . push_back ( X [ i - 1 ] ) ; i -- ; } } while ( i > 0 ) { str . push_back ( X [ i - 1 ] ) ; i -- ; } while ( j > 0 ) { str . push_back ( Y [ j - 1 ] ) ; j -- ; } reverse ( str . begin ( ) , str . end ( ) ) ; return str ; } int main ( ) { string X = " AGGTAB " ; string Y = " GXTXAYB " ; cout << printShortestSuperSeq ( X , Y ) ; return 0 ; }