![LCS[計算機科學算法：最長公共子序列]](/img/8/712/nBnauM3XzYDMyETO2EzM0EDN0UTMyITNykTO0EDMwAjMwUzLxMzLyAzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg "LCS[計算機科學算法：最長公共子序列]")
解決方法
對於一般的LCS問題，都屬於NP問題。當數列的量為一定的時，都可以採用動態規划去解決。
算法
算法名稱：線性DP
動態規劃的一個計算最長公共子序列的方法如下，以兩個序列 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”。
此時，f[i][j]中最大的數便是 X 和 Y 的最長公共子序列的長度，依據該數組回溯，便可找出最長公共子序列。
該算法的空間、時間複雜度均為O(n^2)，經過最佳化後，空間複雜度可為O(n)，時間複雜度為O(nlogn)。
代碼實現
pascal語言實現：
Pascal
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | constmaxlen=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); fori:=1tolength(x)do forj:=1tolength(y)do ifx[i]=y[j]thenc[i,j]:=c[i-1,j-1]+1 elseifc[i-1,j]>c[i,j-1]thenc[i,j]:=c[i-1,j] elsec[i,j]:=c[i,j-1]; z:=""; i:=length(x); j:=length(y); writeln(c[i,j]); while(i>0)and(j>0)do ifx[i]=y[j] thenbeginz:=x[i]+z;i:=i-1;j:=j-1end elseifc[i-1,j]>c[i,j-1]theni:=i-1 elsej:=j-1; ifz<>''thenwriteln(z); fori:=1tolength(x)do begin forj:=1tolength(y)dowrite(c[i][j]:3); writeln; end; readln; end. |
C++語言實現：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<memory.h> constintlcs__xy=100001; intlcs__dp[2][lcs__xy]; longlongbigger(longlongx,longlongy) { returnx>y?x:y; } template<typenamekind>intlcs(kind*x,kind*y,intl1,intr1,intl2,intr2,bool(*equality)(kind,kind)) { if(l1>r1)return0; intnum=(r2+1)*sizeof(kind); memset(lcs__dp[0],0,num); for(inti=l2;i<=r2;i++) if(x[l1]==y[i]) { for(;i<=r2;i++)lcs__dp[0][i]=1; break; } for(inti=++l1,j;i<=r1;i++) { for(j=l2;j<=r2;j++) { if(equality(x[i],y[j]))lcs__dp[1][j]=lcs__dp[0][j-1]+1; elselcs__dp[1][j]=bigger(lcs__dp[0][j],lcs__dp[1][j-1]); } memcpy(lcs__dp[0],lcs__dp[1],num); } returnlcs__dp[0][r2]; } |
