Shortest possible combination 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 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 Code
def printSuperSeq ( a , b ) : NEW_LINE INDENT m = len ( a ) NEW_LINE n = len ( b ) NEW_LINE dp = [ [ 0 ] * ( n + 1 ) for i in range ( m + 1 ) ] NEW_LINE for i in range ( 0 , m + 1 ) : NEW_LINE INDENT for j in range ( 0 , n + 1 ) : NEW_LINE INDENT if not i : NEW_LINE INDENT dp [ i ] [ j ] = j ; NEW_LINE DEDENT elif not j : NEW_LINE INDENT dp [ i ] [ j ] = i ; NEW_LINE DEDENT elif ( a [ i - 1 ] == b [ j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 + min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; NEW_LINE DEDENT DEDENT DEDENT index = dp [ m ] [ n ] ; NEW_LINE res = [ " " ] * ( index ) NEW_LINE i = m NEW_LINE j = n ; NEW_LINE while ( i > 0 and j > 0 ) : NEW_LINE INDENT if ( a [ i - 1 ] == b [ j - 1 ] ) : NEW_LINE INDENT res [ index - 1 ] = a [ i - 1 ] ; NEW_LINE i -= 1 NEW_LINE j -= 1 NEW_LINE index -= 1 NEW_LINE DEDENT elif ( dp [ i - 1 ] [ j ] < dp [ i ] [ j - 1 ] ) : NEW_LINE INDENT res [ index - 1 ] = a [ i - 1 ] NEW_LINE i -= 1 NEW_LINE index -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT res [ index - 1 ] = b [ j - 1 ] NEW_LINE j -= 1 NEW_LINE index -= 1 NEW_LINE DEDENT DEDENT DEDENT ' NEW_LINE INDENT while ( i > 0 ) : NEW_LINE INDENT res [ index - 1 ] = a [ i - 1 ] NEW_LINE i -= 1 NEW_LINE index -= 1 NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT while ( j > 0 ) : NEW_LINE INDENT res [ index - 1 ] = b [ j - 1 ] NEW_LINE j -= 1 NEW_LINE index -= 1 NEW_LINE DEDENT print ( " " . join ( res ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = " algorithm " NEW_LINE b = " rhythm " NEW_LINE printSuperSeq ( a , b ) NEW_LINE DEDENT