[科普中國]-最長公共子序列

定義

最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

定義延伸最長公共子序列（LCS）是一個在一個序列集合中（通常為兩個序列）用來查找所有序列中最長子序列的問題。這與查找最長公共子串的問題不同的地方是：子序列不需要在原序列中占用連續(xù)的位置。而最長公共子串（要求連續(xù)）和最長公共子序列是不同的。2

另外在計算機科學(xué)中，最長遞增子序列是指，在一個給定的數(shù)值序列中，找到一個子序列，使得這個子序列元素的數(shù)值依次遞增，并且這個子序列的長度盡可能地大。最長遞增子序列中的元素在原序列中不一定是連續(xù)的。許多與數(shù)學(xué)、算法、隨機矩陣?yán)碚摚ㄓ⒄Z：random matrix theory）、表示論相關(guān)的研究都會涉及最長遞增子序列。解決最長遞增子序列問題的算法最低要求O(n log n)的時間復(fù)雜度，這里n表示輸入序列的規(guī)模。

復(fù)雜度對于一般性的LCS問題（即任意數(shù)量的序列）是屬于NP-hard。但當(dāng)序列的數(shù)量確定時，問題可以使用動態(tài)規(guī)劃（Dynamic Programming）在多項式時間內(nèi)解決。3

最長公共子序列問題存在最優(yōu)子結(jié)構(gòu)：這個問題可以分解成更小，更簡單的“子問題”，這個子問題可以分成更多的子問題，因此整個問題就變得簡單了。最長公共子序列問題的子問題的解是可以重復(fù)使用的，也就是說，更高級別的子問題通常會重用低級子問題的解。擁有這個兩個屬性的問題可以使用動態(tài)規(guī)劃算法來解決，這樣子問題的解就可以被儲存起來，而不用重復(fù)計算。這個過程需要在一個表中儲存同一級別的子問題的解，因此這個解可以被更高級的子問題使用

應(yīng)用最長公共子序列是一個十分實用的問題，它可以描述兩段文字之間的“相似度”，即它們的雷同程度，從而能夠用來辨別抄襲。對一段文字進行修改之后，計算改動前后文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準(zhǔn)確。簡而言之，百度知道、百度百科都用得上。1

算法動態(tài)規(guī)劃的一個計算兩個序列的最長公共子序列的方法如下：1

以兩個序列 X、Y 為例子：

設(shè)有二維數(shù)組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)當(dāng) X 的第 a 位與 Y 的第 b 位相同時為“1”，否則為“0”。

此時，二維數(shù)組中最大的數(shù)便是 X 和 Y 的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。

該算法的空間、時間復(fù)雜度均為O(n^2)，經(jīng)過優(yōu)化后，空間復(fù)雜度可為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