Longest Common Subsequence

lcs.py

class LCD:
    def __init__(self,s1,s2):
        self.s1 = s1
        self.s2 = s2
        print(s1,s2)

    def solve(self):
        a = [ [ 0 for y in range(len(self.s2)+1) ] for x in range(len(self.s1)+1) ]
        for x in range(len(self.s1)):
            for y in range(len(self.s2)):
                d = 1 if self.s1[x]==self.s2[y] else 0
                a[x+1][y+1] = max(
                        a[x][y]+d,
                        a[x][y+1],
                        a[x+1][y]
                        )

        #for x in a:
        #    print(x)

        print(a[-1][-1])

        self.p(a,len(self.s1),len(self.s2))
        print()

    def p(self,a,i,j):
        #print(i,j)
        if i<0 or j<0:
            return
        if a[i][j]>a[i-1][j] and a[i][j]>a[i][j-1]:
            self.p(a,i-1,j-1)
            print(self.s1[i-1],end=" ")
        else:
            if a[i-1][j]>a[i][j-1]:
                self.p(a,i-1,j)
            else:
                self.p(a,i,j-1)


LCD("abcbdab","bdcaba").solve()
LCD("XMJYAUZ","MZJAWXU").solve()
LCD("9876543210","5432109876").solve()
LCD("101001000100001","100001000100101").solve()
LCD("102003000400005","100002000300405").solve()
LCD("102003000400005","102003000400005").solve()

$ python lcs.py 
abcbdab bdcaba
4
b d a b 
XMJYAUZ MZJAWXU
4
M J A U 
9876543210 5432109876
6
5 4 3 2 1 0 
101001000100001 100001000100101
13
1 0 0 0 1 0 0 0 1 0 0 0 1 
102003000400005 100002000300405
12
1 0 0 0 0 0 0 0 0 0 0 5 
102003000400005 102003000400005
15
1 0 2 0 0 3 0 0 0 4 0 0 0 0 5