Write a Python program that finds the length of the longest

Write a Python program that finds the length of the longest common subsequence of x and y. For example, if x = thecatruns and y = acatran. then the longest common subsequence is r, n and the answer is 5. For this problem, you can define a function lcs(x, y, i, j) to be the length of the longest common subsequence of x[0: i +1] and y[0: j +1].

Solution

I am writing the code in Dynamic programming since if you write it with Recursion, your processing time would be slow.

# Returns length of LCS for X[0..m-1], Y[0..n-1]

def lcs(X, Y, m, n):

    L = [[0 for x in xrange(n+1)] for x in xrange(m+1)]

    # Following steps build L[m+1][n+1] in bottom up fashion. Note

    # that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]

    for i in xrange(m+1):

        for j in xrange(n+1):

            if i == 0 or j == 0:

                L[i][j] = 0

            elif X[i-1] == Y[j-1]:

                L[i][j] = L[i-1][j-1] + 1

            else:

                L[i][j] = max(L[i-1][j], L[i][j-1])

# Following code is used to print LCS

    index = L[m][n]

# Create a character array to store the lcs string

    lcs = [\"\"] * (index+1)

    lcs[index] = \"\\0\"

# Start from the right-most-bottom-most corner and

    # one by one store characters in lcs[]

    i = m

    j = n

    while i > 0 and j > 0:

# If current character in X[] and Y are same, then

# current character is part of LCS

        if X[i-1] == Y[j-1]:

            lcs[index-1] = X[i-1]

            i-=1

            j-=1

            index-=1

# If not same, then find the larger of two and go in the direction of larger value

        elif L[i-1][j] > L[i][j-1]:

            i-=1

        else:

            j-=1

print \"LCS of \" + X + \" and \" + Y + \" is \" + \"\".join(lcs)

# Driver program

X = \"AGGTAB\"

Y = \"GXTXAYB\"

m = len(X)

n = len(Y)

lcs(X, Y, m, n)

Kindly provide feedback.