You are viewing a single comment's thread. Return to all 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)
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Common Subsequence (LCS)
You are viewing a single comment's thread. Return to all comments →