common subsequence
2020-02-09 16:00:50来源:博客园 阅读 ()
common subsequence
求公共最长子序列数目,这种类型不用多想,dp就完了(自我感觉最简单的dp)
首先确定状态,两串字符串比较,所以用二维的dp[i][j]
然后转移方程,当str1[i]=str2[j]时,由两字符串同时加一得到,dp[i][j]=dp[i-1][j-1]+1;
当str1[i]!=str2[j]时,dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
当然需要定义边界条件,比如:i=0或j=0时,dp[0][j]或dp[i][0]=0;
按从小到大的顺序遍历就完了,时间复杂度O(n^2);
然后如果要输出最长公共子序列的时候就倒退,原理懂了很简单(这部分代码注释是掉的)
下面是代码:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string str1,str2;
while(cin>>str1>>str2){
//cin >> str1 >> str2;
int x1=str1.size(),x2=str2.size(),i,j;
vector<int>vec(x1+1,0);
vector<vector<int> > vec1(x2+1,vec);
for(i=0;i<x2;i++){//str2
for(j=0;j<x1;j++){//str1
if(str1[j]==str2[i])vec1[i+1][j+1]=vec1[i][j]+1;
else if(vec1[i+1][j]>vec1[i][j+1])vec1[i+1][j+1]=vec1[i+1][j];
else vec1[i+1][j+1]=vec1[i][j+1];
}
}
cout << vec1[i][j] << endl;
/*
int k=0;
while(i>0&&j>0)
if(vec1[i][j]==vec1[i-1][j])i--;
else if(vec1[i][j]==vec1[i][j-1])j--;
else{
i--,j--;
vec[k++]=j;
}
for(i=k-1;i>=0;i--){
cout << str1[vec[i]];
}
cout << endl;
*/
}
return 0;
}
原文链接:https://www.cnblogs.com/sos3210/p/12287999.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:pearls
- Longest Ordered Subsequence 2020-02-09
- 最长上升子序列(LIS: Longest Increasing Subsequence) 2019-09-08
- HDU 3530Subsequence(单调队列) 2018-09-18
- SPOJ1811 LCS - Longest Common Substring(后缀自动机) 2018-06-27
- C# (Cookie)基本操作 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash