Printing Longest Common Subsequence | Set 2 ( Printing All ) | Maximum string length ; Returns set containing all LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; construct a set to store possible LCS ; If we reaches end of either string , return a empty set ; If the last characters of X and Y are same ; recurse for X [ 0. . m - 2 ] and Y [ 0. . n - 2 ] in the matrix ; append current character to all possible LCS of substring X [ 0. . m - 2 ] and Y [ 0. . n - 2 ] . ; If the last characters of X and Y are not same ; If LCS can be constructed from top side of the matrix , recurse for X [ 0. . m - 2 ] and Y [ 0. . n - 1 ] ; If LCS can be constructed from left side of the matrix , recurse for X [ 0. . m - 1 ] and Y [ 0. . n - 2 ] ; merge two sets if L [ m - 1 ] [ n ] == L [ m ] [ n - 1 ] Note s will be empty if L [ m - 1 ] [ n ] != L [ m ] [ n - 1 ] ; Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Build L [ m + 1 ] [ n + 1 ] in bottom up fashion ; Driver Code
N = 100 NEW_LINE L = [ [ 0 for i in range ( N ) ] for j in range ( N ) ] NEW_LINE def findLCS ( x , y , m , n ) : NEW_LINE INDENT s = set ( ) NEW_LINE if m == 0 or n == 0 : NEW_LINE INDENT s . add ( " " ) NEW_LINE return s NEW_LINE DEDENT if x [ m - 1 ] == y [ n - 1 ] : NEW_LINE INDENT tmp = findLCS ( x , y , m - 1 , n - 1 ) NEW_LINE for string in tmp : NEW_LINE INDENT s . add ( string + x [ m - 1 ] ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if L [ m - 1 ] [ n ] >= L [ m ] [ n - 1 ] : NEW_LINE INDENT s = findLCS ( x , y , m - 1 , n ) NEW_LINE DEDENT if L [ m ] [ n - 1 ] >= L [ m - 1 ] [ n ] : NEW_LINE INDENT tmp = findLCS ( x , y , m , n - 1 ) NEW_LINE for i in tmp : NEW_LINE INDENT s . add ( i ) NEW_LINE DEDENT DEDENT DEDENT return s NEW_LINE DEDENT def LCS ( x , y , m , n ) : NEW_LINE INDENT for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if i == 0 or j == 0 : NEW_LINE INDENT L [ i ] [ j ] = 0 NEW_LINE DEDENT elif x [ i - 1 ] == y [ j - 1 ] : NEW_LINE INDENT L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return L [ m ] [ n ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x = " AGTGATG " NEW_LINE y = " GTTAG " NEW_LINE m = len ( x ) NEW_LINE n = len ( y ) NEW_LINE print ( " LCS ▁ length ▁ is " , LCS ( x , y , m , n ) ) NEW_LINE s = findLCS ( x , y , m , n ) NEW_LINE for i in s : NEW_LINE INDENT print ( i ) NEW_LINE DEDENT DEDENT