首页 > 试题广场 >

最长公共子序列(一)

[编程题]最长公共子序列(一)
  • 热度指数：6856 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car" 、 "aaae" 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。
数据范围 : 。保证字符串中的字符只有小写字母。
要求：空间复杂度 O(n)，时间复杂度
进阶：空间复杂度 O(n)，时间复杂度

输入描述:
第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。
接下来第二行和第三行分别输入一个字符串 s1 和 s2。


输出描述:
输出两个字符串的最长公共子序列的长度
示例1

输入

5 6
abcde
bdcaaa

输出

2

说明

最长公共子序列为 "bc" 或 "bd" ，长度为2   
示例2

输入

3 3
abc
xyz

输出

0
算法知识视频讲解
开通博客
头像 Ivy2019
发表于 2022-10-10 23:38:14
描述 给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。 所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 whoami666
发表于 2022-04-20 19:57:41
Java: 这里使用了char数组，也可以不用char数组，直接用String类的charAt()方法获取单个字符。 import java.util.Scanner; public class Main { public static void main(String[] args) { 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 韭菜牛客
发表于 2022-03-28 14:01:51
描述 给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。 所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 wydxry
发表于 2022-03-03 23:40:13
#include <bits/stdc++.h> using namespace std; const int N=1e3+5; int dp[N][N]={0}; int n,m; string a,b; int main() { cin>>n>>m; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 TomatoHead
发表于 2024-03-15 15:04:38
思路：本题需要处理两个字符串的最长公共子序列（可以不连续），故考虑使用一个二维的dp数组，存储遍历两个字符串时每个子问题对应的最长公共子序列长度解法：用两个变量i和j分别遍历两字符串，不妨对于每个i，都遍历j。对于此时的dp[i][j]，如果此时两字符串中i和j分别指向的元素相等，立刻将dp[i][ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 酱橙~
发表于 2022-04-21 17:14:38
状态方程 dp[i][j] = dp[i - 1][j - 1] + 1; 当str1[i - 1] == str2[j - 1] dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]); str1[i - 1] ！= str2[j - 1] 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客358682707号
发表于 2022-06-15 23:57:40
n = input().split(" ") a = int(n[0]) b = int(n[1]) x = input().strip() y = input().strip() dp = [[0]*(b+1) for _ in range(a+1)] for i in range(a): 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 赫he
发表于 2023-06-19 10:34:18
设dp[i][j]表示 1~i的s1子串和1~j的s2子串的最长公共子序列的最大长度思想：从哪里来如果s1[i]==s2[j]了，那这个f[i][j] = max(f[i][j], f[i-1][j-1]+1)如果s1[i]!=s2[j]f[i][j] <-- max( f[i-1][j], 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客461462035号
发表于 2022-09-12 22:22:52
n,m = map(int,input().split()) s1 = input() s2 = input() dp = [[0]*m for i in range(n)] fo 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客482196251号
发表于 2022-04-06 18:02:39
int main(){ int n,m; scanf("%d %d",&n,&m); char str1[n],str2[m]; scanf("%s",str1); scanf("%s",str2); int dp[n+1][m+1]; 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
20条回答 1112浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号