LCS算法
2021/6/20 11:52:01
本文主要是介绍LCS算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LCS算法
LCS算法:
LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。LCS不是唯一的,它可以有很多种,例如<A,B,C,B,D,A,B>和<B,D,C,A,B,A>的最长子序列可以是<B,C,A,B>也可以是<B,C,B,A>,显然都成立。
问题:
解析:
设Xi=<x1,x2,…,xi>
Yj=<y1,y2,…,yj>
定义两个数组,一个二维数组dp用来存最长序列的长度,而且最终答案一定在dp[strlen(X)][strlen(Y)]上。因为我想求出最长序列,所以又设了一个二维数组c用来存储此位置上两者判断关系,当c=1时表明直接跳过Xi作为最长子序列一员的可能,c=2时换下一个Yj,c=3时表明此时序列配对成功,记录。
这么说可能不是很清楚,接下来的例子可以让你茅塞顿开!!!!!
当X和Y的子序列相等时dp+1,且C = 3,在输出最长子序列时只有当c = 3时才会输出。
下面是源代码:
#include<iostream> #include<cstring> #include<stack> #include<algorithm> #define MAX 1010 using namespace std; int dp[MAX][MAX]; int c[MAX][MAX];//存储删除信息 1删除x,2删除y,3删除两个 int main() { char a[MAX]; char b[MAX]; char temp[MAX]; cout << "===========依次输入两个序列===========" << endl; cin>>a>>b; //获取两条序列长度 int la=strlen(a); int lb=strlen(b); memset(dp,0,sizeof(dp)); memset(c,0,sizeof(c)); for(int i=1; i<=la; i++) { for(int j=1; j<=lb; j++) { if(a[i-1]==b[j-1]) { //序列a=序列b时dp+=1,记录子序列长度 dp[i][j]=dp[i-1][j-1]+1; c[i][j]=3; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); if(dp[i][j-1]>=dp[i-1][j]) c[i][j]=2; else c[i][j]=1; } } } cout<<"===========最长子序列长度为==========="<<dp[la][lb]<<endl; cout<<"=============最长子序列为============" << endl; int m=la,n=lb,i=0; while(m&&n) { if(c[m][n]==1){ a[m--]=' '; } else if(c[m][n]==2) { b[n--]=' '; } else { temp[i++]=a[m-1]; a[m--]=' '; b[n--]=' '; } } for(int j=i-1;j>=0;j--) if(temp[j]!=' ') cout<<temp[j]; cout << endl; return 0; }
这篇关于LCS算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享