-
最長公共子序列
鎖定
- 中文名
- 最長公共子序列
- 外文名
- The longest common subsequence
- 簡 稱
- LCS
- 描 述
- 兩段文字之間的“相似度”
- 分 別
- 是兩個或多個已知序列的子序列
- 計 算
- 改動前後文字的最長公共子序列
- 建議算法
- 動態規劃
- 應用學科
- 數據結構
- 應用領域
- 計算機科學和生物信息學等
最長公共子序列定義
最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
最長公共子序列定義延伸
最長公共子序列（LCS）是一個在一個序列集合中（通常為兩個序列）用來查找所有序列中最長子序列的問題。這與查找最長公共子串的問題不同的地方是：子序列不需要在原序列中佔用連續的位置。而最長公共子串（要求連續）和最長公共子序列是不同的。
[2]
另外在計算機科學中，最長遞增子序列是指，在一個給定的數值序列中，找到一個子序列，使得這個子序列元素的數值依次遞增，並且這個子序列的長度儘可能地大。最長遞增子序列中的元素在原序列中不一定是連續的。許多與數學、算法、隨機矩陣理論（英語：random matrix theory）、表示論相關的研究都會涉及最長遞增子序列。解決最長遞增子序列問題的算法最低要求O(n log n)的時間複雜度，這裏n表示輸入序列的規模。
最長公共子序列複雜度
最長公共子序列問題存在最優子結構：這個問題可以分解成更小，更簡單的“子問題”，這個子問題可以分成更多的子問題，因此整個問題就變得簡單了。最長公共子序列問題的子問題的解是可以重複使用的，也就是説，更高級別的子問題通常會重用低級子問題的解。擁有這個兩個屬性的問題可以使用動態規劃算法來解決，這樣子問題的解就可以被儲存起來，而不用重複計算。這個過程需要在一個表中儲存同一級別的子問題的解，因此這個解可以被更高級的子問題使用
最長公共子序列應用
最長公共子序列是一個十分實用的問題，它可以描述兩段文字之間的“相似度”，即它們的雷同程度，從而能夠用來辨別抄襲。對一段文字進行修改之後，計算改動前後文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準確。簡而言之，百度知道、百度百科都用得上。
[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 的最長公共子序列的長度，依據該數組回溯，便可找出最長公共子序列。
最長公共子序列代碼
最長公共子序列Pascal
const maxlen=200;
var
i,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;
#defineN105
int 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);
}
}
}
- 參考資料
-
- 1. 屈, 婉玲．算法設計與分析：清華大學出版社，2011
- 2. 動態規劃解最長公共子序列問題 ．CSDN[引用日期2016-03-17]
- 3. 鄭翠玲. 最長公共子序列算法的分析與實現[J]. 武夷學院學報, 2010, 29(2):44-48.
