nyoj 36 最长公共子序列（LCS）

「爱情、让人受尽委屈。」 2024-02-17 20:51 1阅读 0赞

### 最长公共子序列 ###

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。  
tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

输入

第一行给出一个整数N(0<N<100)表示待测数据组数  
接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

输出

每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

样例输入

2
    asdf
    adfsd
    123abc
    abc123abc

样例输出

3
    6

分析：最长公共子序列，dp求解，状态方程：dp\[len1\]\[len2\]=dp\[len1-1\]\[len2-1\]+1 ;当s1\[len1-1\]==s2\[len2-1\]；

dp\[len1\]\[len2\]=max(dp\[len1-1\]\[len2\],dp\[len1\]\[len2-1\]); 当s1\[len1-1\]!=s2\[len2-1\]；

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1000+10;
    int dp[maxn][maxn];
    char s1[maxn],s2[maxn];
    int main(){
    	int N;
    	scanf("%d",&N);
    	while(N--){
    		scanf("%s%s",s1,s2);
    		int len1=strlen(s1);
    		int len2=strlen(s2);
    		
    		memset(dp,0,sizeof(dp));
    		for(int i=1;i<=len1;i++){
    			for(int j=1;j<=len2;j++){
    				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]);
    				}
    			}
    		}
    		
    		printf("%d\n",dp[len1][len2]);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关最长公共子序列（LCS）

最长公共子序列（LCS） problem [leetcode: 1035. 不相交的线][leetcode_ 1035.] > dp\[i\]\[j\]：nums

朴灿烈づ我的快乐病毒、/ 2022年10月14日 13:54/ 0 赞/ 175 阅读

相关最长公共子序列（LCS）

这两天编程涉及到求两个字符串的最长公共子序列问题，于是便重新复习之前一直没弄懂的最长公共子序列算法，也算是弄懂了一点。算法分析：采用动态规划方法来解决问题，将最长公共子

分手后的思念是犯贱/ 2022年09月29日 15:52/ 0 赞/ 176 阅读

相关最长公共子序列LCS问题

好久没有写博客了，刚才在网上看了清华大学的数据结构公开课，链接：https://www.xuetangx.com 可以注册个账号去听数据结构课程，老师讲的特好。我的代码是按

冷不防/ 2022年09月17日 15:21/ 0 赞/ 205 阅读

相关 NYOJ 36 最长公共子序列

最长公共子序列时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序

阳光穿透心脏的1/2处/ 2022年08月25日 05:20/ 0 赞/ 96 阅读

相关南阳OJ36-最长公共子序列（LCS）

最长公共子序列时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序

曾经终败给现在/ 2022年08月04日 12:35/ 0 赞/ 148 阅读

相关 LCS 最长公共子序列

首先要明白什么是子序列，什么是子串；设：主串长度为n；子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；

绝地灬酷狼/ 2022年08月03日 14:57/ 0 赞/ 171 阅读

相关最长公共子序列Lcs

1.给出两个字符串A B，求A与B的最长公共子序列的长度（子序列不要求是连续的）。 2.给出两个字符串A B，求A与B的最长公共子序列子串（子序列不要求是连续的）。

浅浅的花香味﹌/ 2022年06月12日 10:55/ 0 赞/ 184 阅读

相关求最长公共子序列（LCS）

题目：求最长公共子序列（LCS）思路：经典的动态规划法， c\[i,j\]表示Xi与Yj的最长公共子序列，其中 Xi = \{x1，、、、xi\}

傷城~/ 2022年05月30日 02:59/ 0 赞/ 198 阅读

相关 nyoj--36--最长公共子序列

最长公共子序列时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共

灰太狼/ 2022年05月26日 06:25/ 0 赞/ 119 阅读

相关 nyoj 36 最长公共子序列（Dp）

最长公共子序列时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序

我就是我/ 2022年04月01日 14:10/ 0 赞/ 220 阅读