动态规划——最长公共子序列

Wu_L7

19148人浏览 · 2022-04-19 22:03:08

Wu_L7 · 2022-04-19 22:03:08 发布

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

#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;
}