Dynamic Program used to find length of longest common subsequences (adopted from http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/)

def lcs(X, Y): # find the length of the strings

m = len(X) n = len(Y) previous = [0] * (len(Y)+1) current = [0] * (len(Y)+1) for i in xrange(m + 1): for j in xrange(n + 1): if i == 0 or j == 0: current[j] = 0

elif X[i - 1] == Y[j - 1]: current[j] = previous[j - 1] + 1

else: current[j] = max(previous[j], current[j - 1]) previous = current current = [0] * (len(Y)+1) return previous[n] X = "AGGTAB"Y = "GXTXAYB"print "Length of LCS is ", lcs(X,Y)