最长公共子序列/子串 LCS(模板)
2023-09-14 08:56:53 时间
首先区分子序列和子串,序列不要求连续性(连续和不连续都可以),但子串一定是连续的
1.最长公共子序列
1、最长公共子序列问题有最优子结构,这个问题可以分解称为更小的问题
2、同时,子问题的解释可以被重复使用的,也就是说更高级别的子问题会重用更小子问题的解。
满足这两点以后,很容易就想到用动态规划来求解。
1.假设两个字符串s1, s2。当其中一个串的长度为0时,公共子序列的长度肯定为0。
2.假设s1的第i个字符与s2的第j个字符相等时,最长子序列等于s1的第i-1个字符与s2的第j-1个字符最长子序列长度+1。
3.假设s1的第i个字符与s2的第j个字符不相等时,最长子序列等于s1的第i个字符与s2的第j-1个字符最长子序列长度或s1的第i-1个字符与s2的第j个字符最
长子序列长度中最大那一个。
dp[i][j]表示s1的第i个字符与s2的第j-1个字符最长子序列长度
#include<iostream> #include<math.h> #include<string.h> using namespace std; int dp[200][200]; int len1,len2; void lcs(string s1,string s2) { for(int i=0;i<=len1;i++)//初始化 dp[i][0]=0; for(int i=0;i<=len2;i++) dp[0][i]=0; 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]); } } } void Print(string s1,string s2)//输出公共子序列 { string str=""; while(len1>=1&&len2>=1)//从字符串s1,s2的末尾位置往前推 { if(s1[len1-1]==s2[len2-1]) { str=str+s1[len1-1]; len1--; len2--; } else { if(dp[len1][len2-1]>dp[len1-1][len2])//说明公共的字符在字符串s1的i位置之前,与字符s2[j]无关 len2--; else len1--; } } for(int i=str.length();i>=0;i--) cout<<str[i]<<' '; cout<<endl; } int main() { string s1,s2; cin>>s1>>s2; len1=s1.length(); len2=s2.length(); lcs(s1,s2); cout<<dp[len1][len2]<<endl; Print(s1,s2); return 0; } // aaeefdhe // saabcd //3 // a a d
2.最长公共子串
最长公共子串跟最长公共子序列的唯一区别在于,公共子串要求是连续的,子序列要求不一定连续。
具体的思路还是动态规划,不同点在于动态规划的迭代策略
#include<iostream> #include<math.h> #include<string.h> using namespace std; int dp[200][200]; int len1,len2; int mx_len=0,End=0;//End是公共字串结束的位置 void lcs(string s1,string s2) { for(int i=0;i<=len1;i++)//初始化 dp[i][0]=0; for(int i=0;i<=len2;i++) dp[0][i]=0; 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]=0; if(dp[i][j]>mx_len) { mx_len=dp[i][j]; End=i-1; } } } } int main() { string s1,s2; cin>>s1>>s2; len1=s1.length(); len2=s2.length(); lcs(s1,s2); cout<<mx_len<<endl; for(int i=End-mx_len+1;i<=End;i++) cout<<s1[i]; cout<<endl; return 0; } // aaeefdhe // saabcd //2 //aa
相关文章
- LeetCode376摆动序列 c++贪心
- 时间序列实践教程总结!
- Python中利用长短期记忆模型LSTM进行时间序列预测分析 - 预测电力负荷数据|附代码数据
- sql查询序列是否存在_oracle if判断是否为空
- Python用KShape对时间序列进行聚类和肘方法确定最优聚类数k可视化|附代码数据
- 最长回文子序列算法详解编程语言
- 利用Oracle循环序列实现快速增量(oracle循环序列)
- 值Oracle取序列值的简单操作(oracle取序列)
- 了解SQL Server中的序列建立(sqlserver建序列)
- 如何使用Oracle建立序列(oracle怎么建序列)
- Oracle中使用序列实现自增长ID(oracle中引用序列)
- 化Redis队列反序列化改变的一切(redis队列反序列)