首页 > 试题广场 >

最长公共子序列(一)

[编程题]最长公共子序列(一)
  • 热度指数：10325 时间限制：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的博客 赞 (7) 回复(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的博客 赞 (3) 回复(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的博客 赞 (2) 回复(0) 收起
头像 TomatoHead
发表于 2024-03-15 15:04:38
思路：本题需要处理两个字符串的最长公共子序列（可以不连续），故考虑使用一个二维的dp数组，存储遍历两个字符串时每个子问题对应的最长公共子序列长度解法：用两个变量i和j分别遍历两字符串，不妨对于每个i，都遍历j。对于此时的dp[i][j]，如果此时两字符串中i和j分别指向的元素相等，立刻将dp[i][ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 韭菜牛客
发表于 2022-03-28 14:01:51
描述 给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。 所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客440904392号
发表于 2024-08-11 21:05:21
#include <bits/stdc++.h> //#include <iostream> //#include <vector> //#include <string> //#include <algorithm> using name 展开全文
去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) 收起
头像 11155454
发表于 2025-04-09 20:29:54
#include <bits/stdc++.h> using namespace std; int main() { int m,n; cin>>m>>n; string s1,s2; cin>>s1>>s 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Gnomeshgh112
发表于 2025-04-08 14:21:16
DP的模板题将s1作为短的字符串，s2作为长的字符串。考虑空间复杂度n*m的做法，定义dp[n][m]，dp[i][j]表示考虑s2的前 i 位和s1的前 j 位的最长公共子序列的结果状态转移：if (s2[i] == s1[j]) dp[i][j] = max(dp[i - 1][j], dp[i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Galaxy_Lee
发表于 2022-06-24 15:29:28
n, m = map(int, input().split()) s1 = input().strip() s2 = input().strip() dp = [[0]*(m+1) for 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

动态规划
难度：
24条回答 1805浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长公共子序列(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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