最長公共子序列

最長公共子序列（LCS）是一個在一個序列集合中（通常為兩個序列）用來查找所有序列中最長子序列的問題。一個數列 ，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則稱為已知序列的最長公共子序列。

最長公共子序列問題是一個經典的計算機科學問題，也是數據比較程式，比如Diff工具，和生物信息學套用的基礎。它也被廣泛地套用在版本控制，比如Git用來調和檔案之間的改變。

基本介紹

• 中文名：最長公共子序列
• 外文名：The longest common subsequence
• 簡稱：LCS
• 描述：兩段文字之間的“相似度”
• 分別：是兩個或多個已知序列的子序列
• 計算：改動前後文字的最長公共子序列
• 建議算法：動態規劃
• 套用學科：數據結構
• 套用領域：計算機科學和生物信息學等

定義

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

定義延伸

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

另外在計算機科學中，最長遞增子序列是指，在一個給定的數值序列中，找到一個子序列，使得這個子序列元素的數值依次遞增，並且這個子序列的長度儘可能地大。最長遞增子序列中的元素在原序列中不一定是連續的。許多與數學、算法、隨機矩陣理論（英語：random matrix theory）、表示論相關的研究都會涉及最長遞增子序列。解決最長遞增子序列問題的算法最低要求O(n log n)的時間複雜度，這裡n表示輸入序列的規模。

複雜度

對於一般性的LCS問題（即任意數量的序列）是屬於NP-hard。但當序列的數量確定時，問題可以使用動態規劃（Dynamic Programming）在多項式時間內解決。

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

套用

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

算法

動態規劃的一個計算兩個序列的最長公共子序列的方法如下：

以兩個序列 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)。

代碼

有三種語言的代碼如下：

Pascal

const 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<cstdlib>#include<cstring>#include<iostream>usingnamespacestd;#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<=len;i++){dp[i][0]=0;dp[0][i]=0;}for(i=1;i<=len1;i++)for(j=1;j<=len2;j++){if(str1[i-1]==str2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=maxx(dp[i-1][j],dp[i][j-1]);}}return dp[len1][len2];}int main(){while(cin>>str1>>str2){int len1=strlen(str1);int len2=strlen(str2);cout<<LCSL(len1,len2)<<endl;}return 0;}

Java

publicclassLCSProblem{publicstaticvoidmain(String[]args){String[]x={"","A","B","C","B","D","A","B"};String[]y={"","B","D","C","A","B","A"};int[][]b=getLength(x,y);Display(b,x,x.length-1,y.length-1);}publicstaticint[][]getLength(String[]x,String[]y){int[][]b=newint[x.length][y.length];int[][]c=newint[x.length][y.length];for(inti=1;i<x.length;i++){for(intj=1;j<y.length;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=0;}else{c[i][j]=c[i][j-1];b[i][j]=-1;}}}returnb;}publicstaticvoidDisplay(int[][]b,String[]x,inti,intj){if(i==0||j==0)return;if(b[i][j]==1){Display(b,x,i-1,j-1);System.out.print(x[i]+"");}elseif(b[i][j]==0){Display(b,x,i-1,j);}elseif(b[i][j]==-1){Display(b,x,i,j-1);}}}