首页 > 代码库 > 最长公共子序列
最长公共子序列
1619: P1050
时间限制: 1 Sec 内存限制: 128 MB提交: 38 解决: 28
[提交][状态][讨论版]
题目描述
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad" ,顺次选1,3,5个字符就构成子串" cad" ,现给定两个字符串,求它们的最长共公子串。
输入
第一行两个字符串用空格分开。
输出
最长子串的长度。
样例输入
abccd aecd
样例输出
3
提示
两个串的长度均小于2000
DP水题,不解释
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int f[2005][2005]; int main() { char char1[2005],char2[2005]; scanf("%s %s",char1+1,char2+1); for(int i=1;i<=strlen(char1+1);i++) for(int j=1;j<=strlen(char2+1);j++) { if(char1[i]==char2[j]) f[i][j]=f[i-1][j-1]+1;else f[i][j]=max(f[i-1][j],f[i][j-1]); } cout<<f[strlen(char1+1)][strlen(char2+1)]<<endl; }
最长公共子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。