Shortest possible combination of two strings | C ++ program to print supersequence of two strings ; Prints super sequence of a [ 0. . m - 1 ] and b [ 0. . n - 1 ] ; Fill table in bottom up manner ; Below steps follow above recurrence ; Following code is used to print supersequence ; Create a string of size index + 1 to store the result ; Start from the right - most - bottom - most corner and one by one store characters in res [ ] ; If current character in a [ ] and b are same , then current character is part of LCS ; Put current character in result ; reduce values of i , j and indexs ; If not same , then find the smaller of two and go in the direction of smaller value ; Copy remaining characters of string ' a ' ; Copy remaining characters of string ' b ' ; Print the result ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printSuperSeq ( string & a , string & b ) { int m = a . length ( ) , n = b . length ( ) ; int dp [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( ! i ) dp [ i ] [ j ] = j ; else if ( ! j ) dp [ i ] [ j ] = i ; else if ( a [ i - 1 ] == b [ 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 ] ) ; } } int index = dp [ m ] [ n ] ; string res ( index + 1 , ' \0' ) ; int i = m , j = n ; while ( i > 0 && j > 0 ) { if ( a [ i - 1 ] == b [ j - 1 ] ) { res [ index - 1 ] = a [ i - 1 ] ; i -- ; j -- ; index -- ; } else if ( dp [ i - 1 ] [ j ] < dp [ i ] [ j - 1 ] ) { res [ index - 1 ] = a [ i - 1 ] ; i -- ; index -- ; } else { res [ index - 1 ] = b [ j - 1 ] ; j -- ; index -- ; } } while ( i > 0 ) { res [ index - 1 ] = a [ i - 1 ] ; i -- ; index -- ; } while ( j > 0 ) { res [ index - 1 ] = b [ j - 1 ] ; j -- ; index -- ; } cout << res ; } int main ( ) { string a = " algorithm " , b = " rhythm " ; printSuperSeq ( a , b ) ; return 0 ; }