锐客网

  1. 首页 > it技术 > >

最长公共子序列

【最长公共子序列】链接：https://ac.nowcoder.com/acm/contest/301/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述 小乐乐有字符串str1,str2。
小乐乐想要给他们找朋友。
小乐乐想知道在这两个字符串中最多能匹配出多长的相同子串（可非连续）。
输入描述:

第一行输入字符串str1; 第二行输入字符串str2; 数据保证字符串长度小于1000，且非空，字符串仅由小写字母组成。

输出描述:
输出最长相同子串的长度。


示例1
输入 复制
asd ad

输出 复制
2

思路：好像没啥死路，直接套模板。如果直接暴力的话，就是每次就从j（0-m）头到尾搜索一下然后在（i++）的两层for循环形式。但用dp的话就快多了（只能说想出dp的人真的厉害！）
借张dp方程的图来说话：
最长公共子序列
文章图片
（显而易见了！）
再借一张路线图来说话：
最长公共子序列
文章图片
（显而易见！）
其次，如果需要输出相同子序列的话，直接二维坐标再加一个参数，用来表示方向，见上图，(6,7)朝上，map[4][4]=1,，(6,6)朝上，map[4][4]=0,向左为-1，以此逆向存储才输出就行了，标记可以和dp全图赋值的时候组合在一起；
#include #include #include #include using namespace std; int dp[1005][1005]; string s1,s2; void Lcs(int n,int m) { for(int i=0; i<=n; i++) dp[i][0]=0; for(int i=0; i<=m; i++) dp[0][i]=0; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; //遇到相等字符 else dp[i][j]=max(dp[i][j-1],dp[i-1][j]); //如果需要输出该子序列，这个可以分开，以方便加参数（方向参数） } } int main() { cin>>s1>>s2; Lcs(s1.length(),s2.length()); cout<

如果还是不理解，可以多看看几篇。推荐其他大佬的博客https://blog.csdn.net/lz161530245/article/details/76943991

    推荐阅读


    上一篇：实现QT android自启动

    下一篇：分块（区间）模板