输入
第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 希望可以帮助到大家