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 ; 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 larger of two and go in the direction of larger value ; Copy remaining characters of string ' a ' ; Copy remaining characters of string ' b ' ; Print the result ; Driver program to test above function
using System ; public class GFG_1 { static void printSuperSeq ( string a , string b ) { int m = a . Length , n = b . Length ; int [ , ] dp = new int [ 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 ( a [ i - 1 ] == b [ j - 1 ] ) dp [ i , j ] = 1 + dp [ i - 1 , j - 1 ] ; else dp [ i , j ] = 1 + Math . Min ( dp [ i - 1 , j ] , dp [ i , j - 1 ] ) ; } } string res = " " ; int k = m , l = n ; while ( k > 0 && l > 0 ) { if ( a [ k - 1 ] == b [ l - 1 ] ) { res = a [ k - 1 ] + res ; k -- ; l -- ; } else if ( dp [ k - 1 , l ] < dp [ k , l - 1 ] ) { res = a [ k - 1 ] + res ; k -- ; } else { res = b [ l - 1 ] + res ; l -- ; } } while ( k > 0 ) { res = a [ k - 1 ] + res ; k -- ; } while ( l > 0 ) { res = b [ l - 1 ] + res ; l -- ; } Console . WriteLine ( res ) ; } public static void Main ( ) { string a = " algorithm " ; string b = " rhythm " ; printSuperSeq ( a , b ) ; } }