先来讲解以下什么是最长公共子序列。最长公共子序列不是最长相同字符串,有点相似但不一样,来举个简单的例子,有字符串s1=bcdea,s2=abce,最长相同字符串是bc,最大公共部分是2;而最长公共子序列则是bce,最大公共部分是3。可以看出,公共子序列不需要连续相等,有相同的序列即可。
明白了概念之后,我们来看一下题目。
2-1 两个字符串的所有最长公共子序列 (转自PTA)
求两个字符串的所有最长公共子序列。
输入格式:
输入长度≤100的两个字符串。
输出格式:
输出两个字符串的所有最长公共子序列,若最长公共子序列多于1个,则将所有子序列按字典序从小到大排序后输出。
输入样例1:
ABCBDAB
BDCABA
输出样例1:
BCAB
BCBA
BDAB
输入样例2:
ABACDEF
PGHIK
输出样例2:
NO
读完题目之后还有点懵的话,那就先听一下我的思路。本题要输出的是最长公共子序列,可能的情况可以分为三种:不存在、只有一条和有多条。如果我们逐个去枚举的话,如果遇到存在多条的情况,是很容易出错并且漏选。那我们可以先求出其最长的长度是多少,再用回溯法,一一找出。
求最大公共子序列的长度
string s1, s2;
int arr[101][101]={0};//动态规划表
set <string> lsc_s;
int lsc_max(int m, int n)//求出最大公共子序列的长度
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s1[i-1]==s2[j-1])arr[i][j]=arr[i-1][j-1]+1;
else arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
}
}
return arr[m][n];
}
s1、s2是要输入的两个字符串,set是集合(后面再讲)。我们怎么来比较呢,设立一个二维表,即上面的arr,字符串s1为纵列,字符串s2为横行。
首先拿出s1中的第一个字符和s2中逐一比较,可得出b行b列的意思是s1中b和s2中ab比较,有1个公共的,故为1;b行c列是s1中b和s2中abc比较,也只有一个公共,也为1;再举一个例子,e行e列是s1中bcde和s2中abce比较,因为e和e相同,并且前面s1中bcd和s2中abc比较时已经有两个公共的了,所以要2+1=3;以此类推,可得出此表,同时我们也可以得出一条递推公式,即
if s1[i]==s2[j],arr[i][j]=arr[i-1][j-1]+1;
else arr[i][j]=max{ arr[i][j-1], arr[i-1][j] };
即可得出最长公共子序列的最大长度arr[i][j]。下一步就可根据回溯法来获取公共子序列的所有序列并打印。
打印所有最长公共子序列
void lsc_print(int i, int j, string str)
{
while(i>0&&j>0)
{
if(s1[i-1]==s2[j-1])
{
i--;
j--;
str=s1[i]+str;
}
else
{
if(arr[i-1][j]>arr[i][j-1])i--;
else if(arr[i-1][j]<arr[i][j-1])j--;
else
{
lsc_print(i-1,j,str);
lsc_print(i,j-1,str);
return;
}
}
}
if(str.length())lsc_s.insert(str);
}
从arr[i][j]开始回溯,当s1[i-1]==s2[j-1]时,说明此公共子序列中包括这个元素,即可把这个元素加入到临时变量str中(头插法),因为是回溯,满足条件的元素在前面;当s1[i-1]!=s2[j-1]时,说明arr[i][j]是由arr[i-1][j]或者arr[i][j-1]继承而来,所以可以判断这两个哪个比较大,就跑去那边,当两边一样大的时候,说明可能存在不同的最长子序列,所以可以进行递归分别求解。当回溯完成后,把str放入到set容器中储存起(为什么用set不用数组,因为题目要求按字典序从小到大输出,set底层是红黑树,自动帮我们排列好,感兴趣的同学可以去看看set用法和底层操作)。
最终ac代码如下:文章来源:https://www.toymoban.com/news/detail-418204.html
#include<iostream>
#include<string>
#include<set>
using namespace std;
string s1, s2;
int arr[101][101]={0};//动态规划表
set <string> lsc_s;
int lsc_max(int m, int n)//求出最大公共子序列的长度
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s1[i-1]==s2[j-1])arr[i][j]=arr[i-1][j-1]+1;
else arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
}
}
return arr[m][n];
}
void lsc_print(int i, int j, string str)
{
while(i>0&&j>0)
{
if(s1[i-1]==s2[j-1])
{
i--;
j--;
str=s1[i]+str;
}
else
{
if(arr[i-1][j]>arr[i][j-1])i--;
else if(arr[i-1][j]<arr[i][j-1])j--;
else
{
lsc_print(i-1,j,str);
lsc_print(i,j-1,str);
return;
}
}
}
if(str.length())lsc_s.insert(str);
}
int main()
{
cin>>s1>>s2;
int m=s1.length();
int n=s2.length();
int len=lsc_max(m,n);
string str;
lsc_print(m, n, str);
set<string>::iterator it=lsc_s.begin();
if(lsc_s.empty())
{
cout<<"NO"<<endl;
return 0;
}
while(it!=lsc_s.end())
{
cout<<*it<<endl;
it++;
}
return 0;
}
如果本篇文章对你有所帮助的话,记得点赞哦!如果哪里写得不好的话,也可以评论,欢迎指正!文章来源地址https://www.toymoban.com/news/detail-418204.html
到了这里,关于动态规划——最长公共子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!