天天看点

最长公共子序列问题代码展示

输入

第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)      

输出

输出最长的子序列,如果有多个,随意输出1个。      

输入示例

abcicba
abdkscab      

输出示例

abca      

问题and教程来源:http://www.51nod.com/tutorial/course.html#!courseId=4

其实对于最长公共子序列的问题,网上都有非常非常多平易近人、好的教程,在这里就不多赘述啦~只想和大家分享一些我看完之后的小体会。

最长公共子序列其实也是一道动态规划的题目。是动态规划的题目那么肯定就有属于它的状态转移方程。

针对它的动态转移方程,其实也可以用我们之前说道的“潜在终点”的思维。

首先,我们有两个序列 

A1 A2 A3......Am

B1B2 B3......Bn

首先我们需要明确的是,A和B序列长度不一定一样噢!

然后我们分别取两个序列中的子串(连续的)

A1.......Ax

B1.......By

我们想想,这两个子串都是连续的,而且各自有自己的结尾,Ax和By,作为自己的“终点元素”,倘若,Ax=By,是不是说明,我们针对这两个子串的最长公共子序列一定要包含这个元素?

我们不妨用LCD(Ax,By)来表示,当前两个子串的最长公共子序列。是不是LCD(Ax,By)=LCD(Ax-1,By-1)

wait a minute

是不是快晕了。

不要着急,我们想一下,因为Ax=By,所以我们不管它们啦,它们的恩恩怨怨爱恨离愁都不管了,因为肯定要包含的。

假如我们不包含它

那么我们针对这两个子串的最长公共子序列再加上Ax或者By,是不是还能形成“更长”的公共子序列,所以矛盾。所以我们的最长公共子序列必须要以Ax或者By结尾。

注意!我们得到了LCD(Ax,By)=LCD(Ax-1,By-1)

把目前的问题,转移到前面的Ax-1和By-1的问题上

然后,假如我们的Ax不等于By呢?

也就是说,我们的LCD(Ax,By)的“终点元素”可能

等于Ax不等于By

等于By不等于Ax

既不等于Ax也不等于By

wait a minute

是不是快晕了

我们放下脚步,我们现在要求最长公共子序列对吧,

因为我们拿不准,究竟是取Ax还是取By还是两个都不取我们的最终元素。那么我们围绕最长,是不是应该做一个比较,例如序列abc和ccd,c和d不相等噢!那么我们就比较一下嘛,看一下

abc

和cc(ccd忽略了d,假设不关d的事)的最长公共子序列-----c 长度为1

ab(abc忽略了c,假设不关c的事)

和ccd的最长公共子序列------长度为0

所以此时我们取大的,最长公共子序列为c,长度为1

注意!我们得到了LCD(Ax,By)=max(LCD(Ax-1,By),LCD(Ax,By-1))

把目前的问题,转移到前面的Ax-1或By-1的问题上

或许你还是不服气,说我们只考虑了不等于Ax等于By或者等于Ax不等于By的情况啊,如果两个都不等于呢?为什么不来个Ax-1,By-1

我们来分析一下

LCD Ax-1,By-1和LCD Ax-1,By和LCD Ax,By-1有没有比较的必要。。。。。。

你觉得Ax-1,By-1的最长公共子序列会比它们长吗。。。。。。

我觉得肯定不可能吧

而且,我们

LCD(Ax-1,By),LCD(Ax,By-1)其实已经包含了Ax和By都不包含的情况,你想一下,假如都不包含,那么是不是考虑不考虑这个元素也没关系

但是我们假如都不考虑,那就出问题了,因为我们抹杀掉可能“终点元素”就是其中之一的可能性!

总而言之,看到x-1,y-1这些东西,可以形象的想成“不关这个元素的事”

好了,我们得到了我们的状态转移方程,有没有觉得它像一个东西。。。。。。 没错,它跟矩阵取数有点像,都是可能根据左方和上方,在这里还可能根据“斜上方”,但是做法大同小异。

代码展示

因为要追踪生成的最大公共子序列是多少,所以我定义了个road数组,如果上 左对应了1和4 左上方代表了5; 然后为了整体的下标统一,我把一开始输入的a和b都往后挪了个位置。

#include<iostream>
#include<string>
using namespace std;	
int dp[1001][1001];
int road[1001][1001];
int main()
{
		string a;
		string b;
		while(cin>>a)
		{
			cin>>b;
			string common;
			a=a+'a';
			b=b+'b';
			for(int i=0;i<1001;i++)
			{
				for(int j=0;j<1001;j++)
				road[i][j]=0;
			}
			for(int i=a.size()-1;i>=1;i--)
			{
				a[i]=a[i-1];
			}			
			for(int i=b.size()-1;i>=1;i--)
			{
				b[i]=b[i-1];
			}
			for(int j=0;j<1001;j++)
			dp[0][j]=0;
			for(int i=0;i<1001;i++)
			dp[i][0]=0;
			int l1=a.size();
			int l2=b.size();
			for(int i=1;i<l1;i++)
			{
				for(int j=1;j<l2;j++)
				{
					if(a[i]==b[j])
					{
						dp[i][j]=dp[i-1][j-1]+1;
						road[i][j]=5;
					}
					else
					{
						if(dp[i-1][j]>=dp[i][j-1])
						{
							dp[i][j]=dp[i-1][j];
							road[i][j]=1;
						}
						else
						{
							dp[i][j]=dp[i][j-1];
							road[i][j]=4;
						}
					}
				}
			}
			for(int i=a.size()-1,j=b.size()-1;i>0&&j>0;)
			{
				if(road[i][j]==1)
				{
					i=i-1;
					continue;
				}
				if(road[i][j]==4)
				{
					j=j-1;
					continue;
				}
				if(road[i][j]==5)
				{
					common=common+a[i];
					i=i-1;
					j=j-1;	
					continue;
				}
			}
			for(int i=common.size()-1;i>=0;i--)
			cout<<common[i];
			cout<<endl;
		}	
}
           

其实我也不知道自己讲那么多能不能帮助大家理解T-T 希望可以帮助到大家