LCS

#Longest Common Subsequence
'''
def LCSrec(i,j): # Using top-down recursive approach(without memoization)
    if i==maxa or j==maxb:
        return 0
    if a[i]==b[j]:
        return 1+LCS(i+1,j+1)
    else:
        return max(LCS(i+1,j),LCS(i,j+1))
'''
s1=input("Enter the first word{THE LONGER WORD}\n") #dp approach
s2=input("Enter the second word\n")
s1l=len(s1)
s2l=len(s2)
comb=[[0 for i in range(s1l+1)] for j in range(s2l+1)]
for i in range(s2l):
	for j in range(s1l):
		if s2[i]==s1[j]:
			comb[i+1][j+1]=comb[i][j]+1
		else:
			comb[i+1][j+1]=max(comb[i][j+1],comb[i+1][j])
#print(comb)
print("Length of the LCS: ",comb[s2l][s1l])
i=s2l
j=s1l
p=""
while i>=0:
	if i==0 and j==0:
		break
	while j>=0:
		if comb[i][j]==comb[i][j-1]:
			j-=1
		elif comb[i][j]==comb[i-1][j]:
			i-=1
			break
		else:
			req=s1[j-1]
			p=req+p
			i-=1
			j-=1
			#print(p)
			break
print("LCS: ",p)