16.longest_common_subsequence

#16. Write a program to find the length of the longest common subsequence between two strings.
"""
potato tomato
length of s1 6
length of s2 6
length= 4
"""

def longest_common_subsequence(s1,s2,m,n):
    dp=[[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if(s1[i-1]==s2[j-1]):
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[m][n]

s1,s2=map(str,input().split(" "))
m=int(input())
n=int(input())
print("length=",longest_common_subsequence(s1,s2,m,n))