最長公共子序列

最長公共子序列

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

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

基本介紹

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

定義

最長公共子序列,英文縮寫為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);}}}

相關詞條

熱門詞條

聯絡我們