第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。接下来第二行和第三行分别输入一个字符串 s1 和 s2。
输出两个字符串的最长公共子序列的长度
5 6 abcde bdcaaa
2
最长公共子序列为 "bc" 或 "bd" ，长度为2
3 3 abc xyz
0
n1,n2 = list(map(int,input().split())) s1 = input() s2 = input() def common(s1,s2): #dp[i][j]为s1[...i]和s2[...j]的最长公共子序列,这里包括索引i和j #dp[i][j]为s1到索引i,s2到索引j的最长公共子序列 n1 = len(s1) n2 = len(s2) dp = [[0]*(n2) for _ in range(n1)] if s1[0]==s2[0]: dp[0][0]=1 for i in range(n1): if s2[0] in s1[:i+1]: dp[i][0]=1 for j in range(n2): if s1[0] in s2[:j+1]: dp[0][j]=1 for i in range(1,n1): for j in range(1,n2): if s1[i]==s2[j]: dp[i][j] = dp[i-1][j-1]+1 else: dp[i][j] = max(dp[i-1][j],dp[i][j-1]) return dp[n1-1][n2-1] res = common(s1,s2) print(res)方法2：
n1,n2 = list(map(int,input().split())) s1 = input() s2 = input() def common(s1,s2): #dp[i][j]为s1[...i-1]和s2[...j-1]的最长公共子序列,这里包括索引i-1和j-1，不包括索引i和j,即s1[:i],s2[:j] #dp[i][j]为s1截至到第i个字符，s2截至到第j个字符的最长公共子序列 n1 = len(s1) n2 = len(s2) dp = [[0]*(n2+1) for _ in range(n1+1)] for i in range(1,n1+1): for j in range(1,n2+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[n1][n2] res = common(s1,s2) print(res)
import sys def longnums(str1): if(len(str1) != 0): nums1 = str1[1] nums2 = str1[0] len1 = len(nums1) len2 = len(nums2) dp = [[0 for col in range(len2+1)] for row in range(len1+1)] for i in range(1,len1+1): for j in range(1,len2+1): if(nums1[i-1] == nums2[j-1]): dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i][j-1],dp[i-1][j]) return dp[len1][len2] str1 = [] for line in sys.stdin: a = line.split() str1 = a + str1 print(longnums(str1))
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
