&＃xff08;1&＃xff09;子序列&＃xff1a; 一个序列A &＃xff1d; a1,a2,……an,中任意删除若干项&＃xff0c;剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。
例如&＃xff1a;
对于一个长度为n的序列&＃xff0c;它一共有2^n 个子序列&＃xff0c;有(2^n – 1)个非空子序列。
请注意&＃xff1a;子序列不是子集&＃xff0c;它和原始序列的元素顺序是相关的。
&＃xff08;2&＃xff09;公共子序列 &＃xff1a; 顾名思义&＃xff0c;如果序列C既是序列A的子序列&＃xff0c;同时也是序列B的子序列&＃xff0c;则称它为序列A和序列B的公共子序列。
例如&＃xff1a;
序列1,8,7是它们的一个公共子序列。
请注意&＃xff1a; 空序列是任何两个序列的公共子序列。
仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5
它们的最长公共子序列是&＃xff1a;
1,4,8,7
1,4,6,7
请注意: 最长公共子序列不唯一。
请大家用集合的观点来理解这些概念&＃xff0c;子序列、公共子序列以及最长公共子序列都不唯一&＃xff0c;所以我们通常说一个最长公共子序列&＃xff0c;但显然最长公共子序列的长度是一定的。
最长公共子序列问题就是求序列A&＃61; a1,a2,……an, 和B &＃61; b1,b2,……bm,的一个最长公共子序列。
因为最长公共子序列不唯一&＃xff0c;让我们把问题简化&＃xff0c;如何求出两个序列的最长公共子序列长度呢&＃xff1f;
你首先能想到的恐怕是暴力枚举&＃xff1f;那我们先来看看&＃xff1a;序列A有 2^n 个子序列&＃xff0c;序列B有 2^m 个子序列&＃xff0c;如果任意两个子序列一一比较&＃xff0c;比较的子序列高达 2^(n&＃43;m) 对&＃xff0c;这还没有算具体比较的复杂度。
或许你说&＃xff0c;只有长度相同的子序列才会真正进行比较。那么忽略空序列&＃xff0c;我们来看看&＃xff1a;对于A长度为1的子序列有C(n,1)个&＃xff0c;长度为2的子序列有C(n,2)个&＃xff0c;……长度为n的子序列有C(n,n)个。对于B也可以做类似分析&＃xff0c;即使只对序列A和序列B长度相同的子序列做比较&＃xff0c;那么总的比较次数高达&＃xff1a;
C(n,1)*C(m,1)*1 &＃43; C(n,2) * C(m,2) * 2&＃43; …&＃43;C(n,p) * C(m,p)*p
吓着了吧&＃xff1f;怎么办&＃xff1f;试试使用动态规划算法&＃xff01;
让我们来看看如何求LCS(x, y)。我们令x表示子序列考虑最后一项
&＃xff08;1&＃xff09; Ax &＃xff1d; By
则要么L(x,y)为空序列&＃xff08;别忘了这个&＃xff09;&＃xff0c;要么L(x,y)的最后一项是Aa&＃xff1d;Bb ≠ t, 且显然有a
如果我们从序列Ax中删掉最后一项ax得到Ax-1,从序列By中也删掉最后一项by得到By-1&＃xff0c;(多说一句角标为0时&＃xff0c;认为子序列是空序列)&＃xff0c;则我们从L(x,y)也删掉最后一项t得到的序列是L(x – 1, y - 1)。为什么呢&＃xff1f;和上面的道理相同&＃xff0c;如果得到的序列不是L(x - 1, y - 1)&＃xff0c;则它一定比L(x - 1, y - 1)短&＃xff08;注意L&＃xff08;&＃xff0c;&＃xff09;是个集合&＃xff01;&＃xff09;&＃xff0c;那么它后面接上元素t得到的子序列L(x,y)也比L(x - 1, y - 1)接上元素t得到的子序列短&＃xff0c;这与L(x, y)是最长公共子序列矛盾。
仍然设t &＃61; L(Ax, By), 或者L(Ax, By)是空序列&＃xff08;这时t是未定义值不等于任何值&＃xff09;。
则t ≠ Ax和t ≠ By至少有一个成立&＃xff0c;因为t不能同时等于两个不同的值嘛&＃xff01;
&＃xff08;2.1&＃xff09; 如果t ≠ Ax&＃xff0c;则有L(x, y)&＃61; L(x - 1, y)&＃xff0c;因为根本没Ax的事嘛。
LCS(x,y) &＃61; LCS(x – 1, y)
&＃xff08;2.2&＃xff09; 如果t ≠ By,l类似L(x, y)&＃61; L(x , y - 1)
可是&＃xff0c;我们事先并不知道t&＃xff0c;由定义&＃xff0c;我们取最大的一个&＃xff0c;因此这种情况下,有LCS(x,y) &＃61; max(LCS(x – 1, y) , LCS(x, y – 1))。
看看目前我们已经得到了什么结论&＃xff1a;
LCS(x,y) &＃61;
(1) LCS(x - 1,y - 1) &＃43; 1 如果Ax &＃xff1d; By
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
这时一个显然的递推式&＃xff0c;光有递推可不行&＃xff0c;初值是什么呢&＃xff1f;
显然&＃xff0c;一个空序列和任何序列的最长公共子序列都是空序列&＃xff01;所以我们有:
(1) LCS(x - 1,y - 1) &＃43; 1 如果Ax &＃xff1d; By
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
(3) 0 如果x &＃61; 0或者y &＃61; 0
到此我们求出了计算最长公共子序列长度的递推公式。我们实际上计算了一个(n &＃43; 1)行(m &＃43; 1)列的表格&＃xff08;行是0..n&＃xff0c;列是0..m)&＃xff0c;也就这个二维度数组LCS(,)。
输入序列A, B长度分别为n&＃xff0c;m,计算二维表 LCS(int,int):
for x &＃61; 0 to n do
for y &＃61; 0 to m do
if (x &＃61;&＃61; 0 || y &＃61;&＃61; 0) then
LCS(x, y) &＃61; 0
else if (Ax &＃61;&＃61; By) then
LCS(x, y) &＃61; LCS(x - 1,y - 1) &＃43; 1
else
LCS(x, y) &＃61; ) max(LCS(x – 1, y) , LCS(x, y – 1))
endif
endfor
endfor
现在问题来了&＃xff0c;我们如何得到一个最长公共子序列而仅仅不是简单的长度呢&＃xff1f;其实我们离真正的答案只有一步之遥&＃xff01;
&＃xff08;1&＃xff09; LCS(x – 1, y – 1) &＃43; 1如果Ax &＃xff1d; By
这对应L(x,y) &＃61; L(x,- 1 y- 1)末尾接上Ax
&＃xff08;2.1&＃xff09; LCS(x – 1, y) 如果Ax ≠ By且LCS(x – 1, y) ≥LCS(x, y – 1)
这对应L(x,y)&＃61; L(x – 1, y)
&＃xff08;2.2&＃xff09; LCS(x, y – 1) 如果Ax ≠ By且LCS(x – 1, y)
&＃xff08;3&＃xff09; 0 如果 x &＃61;0或者y &＃61; 0
这对应L(x,y)&＃61;空序列
注意(2.1)和(2.2) &＃xff0c;当LCS(x – 1, y) &＃xff1d; LCS(x, y – 1)时&＃xff0c;其实走哪个分支都一样&＃xff0c;虽然长度时一样的&＃xff0c;但是可能对应不同的子序列&＃xff0c;所以最长公共子序列并不唯一。
神奇吧&＃xff1f;又一个类似的递推公式。可见我们在计算长度LCS(x,y)的时候只要多记录一些信息&＃xff0c;就可以利用这些信息恢复出一个最长公共子序列来。就好比我们在迷宫里走路&＃xff0c;走到每个位置的时候记录下我们时从哪个方向来的&＃xff0c;就可以从终点回到起点一样。
时间复杂度时O(n * m)&＃xff0c;空间也是O(n * m)
今天对LCS的讲解就到这里&＃xff0c;聪明的你是不是已经蠢蠢欲动要AC问题啦&＃xff1f; 心动不如行动&＃xff0c;赶快吧。
最后&＃xff0c;我们来提供输入输出数据&＃xff0c;由你来写一段程序&＃xff0c;实现这个算法&＃xff0c;只有写出了正确的程序&＃xff0c;才能继续后面的课程。
第1行&＃xff1a;字符串A
第2行&＃xff1a;字符串B
(A,B的长度 <&＃61; 1000)
输出最长的子序列&＃xff0c;如果有多个&＃xff0c;随意输出1个。
abcicba
abdkscab
输出示例
abca
代码
#include
#include
#include<string>using namespace std;string ans[1001],a,b;
int w,i,j,dp[1001][1001];
int main()
{cin>>a>>b;for(i&＃61;1;i<&＃61;a.length() ;&＃43;&＃43;i){for(j&＃61;1;j<&＃61;b.length() ;&＃43;&＃43;j){if(a[i-1]&＃61;&＃61;b[j-1]) dp[i][j]&＃61;dp[i-1][j-1]&＃43;1;else {if(dp[i][j-1]>&＃61;dp[i-1][j])dp[i][j]&＃61;dp[i][j-1];else dp[i][j]&＃61;dp[i-1][j];}}}for(i&＃61;a.length(),j&＃61;b.length();i>&＃61;1&&j>&＃61;1;){if(a[i-1]&＃61;&＃61;b[j-1]){ans[w&＃43;&＃43;]&＃61;a[i-1];i--;j--;}else {if(dp[i][j-1]>dp[i-1][j]){j--;}else i--;}}for(j&＃61;w-1;j>&＃61;0;--j)cout<<ans[j];cout<<endl;return 0;
}
&＃xff08;来源于51nod教程&＃xff09;。
转:https://www.cnblogs.com/ruojisun/p/6070371.html
京公网安备 11010802041100号