Printing Shortest Common Supersequence | 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 Code
def printShortestSuperSeq ( x , y ) : NEW_LINE INDENT m = len ( x ) NEW_LINE n = len ( y ) NEW_LINE dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if i == 0 : NEW_LINE INDENT dp [ i ] [ j ] = j NEW_LINE DEDENT elif j == 0 : NEW_LINE INDENT dp [ i ] [ j ] = i NEW_LINE DEDENT elif x [ i - 1 ] == y [ 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 string = " " NEW_LINE i = m NEW_LINE j = n NEW_LINE while i > 0 and j > 0 : NEW_LINE INDENT if x [ i - 1 ] == y [ j - 1 ] : NEW_LINE INDENT string += x [ i - 1 ] NEW_LINE i -= 1 NEW_LINE j -= 1 NEW_LINE DEDENT elif dp [ i - 1 ] [ j ] > dp [ i ] [ j - 1 ] : NEW_LINE INDENT string += y [ j - 1 ] NEW_LINE j -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT string += x [ i - 1 ] NEW_LINE i -= 1 NEW_LINE DEDENT DEDENT while i > 0 : NEW_LINE INDENT string += x [ i - 1 ] NEW_LINE i -= 1 NEW_LINE DEDENT while j > 0 : NEW_LINE INDENT string += y [ j - 1 ] NEW_LINE j -= 1 NEW_LINE DEDENT string = list ( string ) NEW_LINE string . reverse ( ) NEW_LINE return ' ' . join ( string ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x = " AGGTAB " NEW_LINE y = " GXTXAYB " NEW_LINE print ( printShortestSuperSeq ( x , y ) ) NEW_LINE DEDENT