先来讲解以下什么是最长公共子序列。最长公共子序列不是最长相同字符串，有点相似但不一样，来举个简单的例子，有字符串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模板网！
