The Longest Common Subsequence (LCS) Discussions | Tutorials | HackerRank
  • + 0 comments
    def lcs(x,y,m,n):
        t=[[0 for i in range(n+1)] for i in range(m+1)]
        
        for i in range(n+1):
            t[0][i]=0
        for i in range(m+1):
            t[i][0]=0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if x[i-1] == y[j-1]:
                    t[i][j]=1+t[i-1][j-1]
                else:
                    t[i][j]=max(t[i-1][j],t[i][j-1])
        index=t[m][n]
        i=m
        j=n
        lcs=['']*(index+1)
        lcs[index]=''
        while i > 0 and j >0:
            if x[i-1] == y[j-1]:
                lcs[index-1]=x[i-1]
                i=i-1
                j=j-1
                index=index-1
            elif t[i-1][j] > t[i][j-1]:
                i=i-1
            else:
                j=j-1
        print(' '.join(lcs))
    ab=input().split()
    x=input().split()
    y=input().split()
    m=len(x)
    n=len(y)
    lcs(x,y,m,n)