Longest Common Subsequence | DP | Dynamic Programming implementation of LCS problem ; Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion Note : L [ i ] [ j ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; L [ m ] [ n ] contains the length of LCS of X [ 0. . n - 1 ] & Y [ 0. . m - 1 ] ; end of function lcs Driver program to test the above function
def lcs ( X , Y ) : NEW_LINE INDENT m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE L = [ [ None ] * ( n + 1 ) for i in xrange ( m + 1 ) ] NEW_LINE 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 X = " AGGTAB " NEW_LINE Y = " GXTXAYB " NEW_LINE print " Length ▁ of ▁ LCS ▁ is ▁ " , lcs ( X , Y ) NEW_LINE