# input: a[0..M) and b[0..N), M>=0 and N>=0## output: length of a longest common subsequence of a[0..M) and# b[0..N)## O(MN) time and space solutiondeflcs_tab(a,b):M,N=len(a),len(b)tab=[[0forninrange(N+1)]forminrange(M+1)]m,n=1,1whilem!=M+1:ifn==N+1:m,n=m+1,1else:ifa[m-1]==b[n-1]:tab[m][n]=1+tab[m-1][n-1]else:tab[m][n]=max(tab[m][n-1],tab[m-1][n])n+=1returntab[M][N]
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.