[科普中国]-最长公共子序列

定义

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

定义延伸最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置。而最长公共子串（要求连续）和最长公共子序列是不同的。2

另外在计算机科学中，最长递增子序列是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论（英语：random matrix theory）、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O(n log n)的时间复杂度，这里n表示输入序列的规模。

复杂度对于一般性的LCS问题（即任意数量的序列）是属于NP-hard。但当序列的数量确定时，问题可以使用动态规划（Dynamic Programming）在多项式时间内解决。3

最长公共子序列问题存在最优子结构：这个问题可以分解成更小，更简单的“子问题”，这个子问题可以分成更多的子问题，因此整个问题就变得简单了。最长公共子序列问题的子问题的解是可以重复使用的，也就是说，更高级别的子问题通常会重用低级子问题的解。拥有这个两个属性的问题可以使用动态规划算法来解决，这样子问题的解就可以被储存起来，而不用重复计算。这个过程需要在一个表中储存同一级别的子问题的解，因此这个解可以被更高级的子问题使用

应用最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。1

算法动态规划的一个计算两个序列的最长公共子序列的方法如下：1

以两个序列 X、Y 为例子：

设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：

f[1][1] = same(1,1);

f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]};

其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”，否则为“0”。

此时，二维数组中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。

该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)。2

代码有三种语言的代码如下：2

Pascalconst maxlen=200;vari,j:longint;c:array[0..maxlen,0..maxlen]ofbyte;x,y,z:string;{z为x,y的最长公共子序列}begin readln(x); readln(y); fillchar(c,sizeof(c),0); for i:=1 to length(x) do for j:=1 to length(y) do if x[i]=y[j] then c[i,j]:=c[i-1,j-1]+1 else if c[i-1,j]>c[i,j-1] then c[i,j]:=c[i-1,j] else c[i,j]:=c[i,j-1]; z:=''; i:=length(x); j:=length(y); writeln(c[i,j]); while (i>0)and(j>0) do if x[i]=y[j] then begin z:=x[i]+z;i:=i-1;j:=j-1 end else if c[i-1,j]>c[i,j-1] then i:=i-1 else j:=j-1; if z'' then writeln(z); for i:=1 to length(x)do begin for j:=1 to length(y) do write(c[i][j]:3); writeln; end; readln;end.C++#include#include#includeusingnamespacestd;#defineN105int dp[N+1][N+1];char str1[N],str2[N];int maxx(int a,int b){if(a>b)return a;return b;}int LCSL(int len1,int len2){int i,j;int len=maxx(len1,len2);for(i=0;i>str2){int len1=strlen(str1);int len2=strlen(str2);cout