lcs.py

def lcs(str1, str2):
    l = [[0] * len(str2) for i in range(len(str1))]

    for r in range(len(str1)):
        for c in range(len(str2)):
            if r > 0 and c > 0:
                l[r][c] = max(l[r-1][c], l[r][c-1])
                if str1[r] == str2[c]:
                    l[r][c] = max(l[r - 1][c - 1] + 1, l[r][c])
            if r == 0 or c == 0:
                if r == 0 and c > 0:
                    l[r][c] = max(l[r][c], l[r][c - 1])
                if c == 0 and r > 0:
                    l[r][c] = max(l[r-1][c], l[r][c])
                if str1[r] == str2[c]:
                    l[r][c] = max(1, l[r][c])
    return l[len(str1) - 1][len(str2) - 1]