關于最長公共子序列(LCS)
最長公共子序列和最長公共子串是有差別的,之前我一直把它們混淆。
-
最長公共子串舉例:假設S1={A,D,C,B,E,X,Q},S2={H,P,D,C,B,E,M,L}
那麼它們的最長公共子串就是{D,C,B,E}。這是我通常了解的東西。
最長公共子序列。
- 最長公共子序列舉例:假設S1={A,B,C,A,D,A,B},S2={B,A,C,D,B,A},那麼它們的LCS就是{B,A,D,B}。
求解最長公共子序列
這是一個動态規劃問題。如何求解最長公共子序列(以下用LCS代替)呢?我們假設已經知道Z={z1,z2,...zk}是X={x1,x2,...,xm}和Y={y1,y2,...,yn}的LCS,那麼可以分以下三種情況讨論(具體每種情況證明不再累述):
- xm=yn=zk:那麼Zk-1是Xm-1和Yn-1的LCS。
- xm≠yn,yn≠zk:我們可以把yn去掉,那麼Zk是Xm和Yn-1的LCS。
- xm≠yn,xm≠zk:我們可以把xm去掉,那麼Zk是Xm-1和Yn的LCS。
基于以上情況,我們可以得到LCS遞歸式。我們假設ci表示Xi和Yi的LCS長度,那麼:
- ci=0(i=0或j=0);
- ci=c[i-1]c[j-1]+1(i,j>0且xi=yi);
- ci=max{ci-1,c[i],[j-1]};(i,j>0且xi≠yi)。
這樣我們就可以得到LCS的長度。如何得到具體内容是什麼呢?我們可以借用一個輔助數組bi,這個數組用來記錄ci的來源,分别有如下情況:
- ci=ci-1+1,則bi=1;
- ci=ci,則bi=2;
- ci=ci-1,則bi=3。
這樣就可以根據bm反向追蹤LCS,當bi=1,輸出xi;當bi=2,追蹤ci;當bi=3,追蹤ci-1,直到i=0或j=0停止。
算法設計
(1)初始化。初始化c[][]第1行和第1列為0。
(2)開始操作。具體是将s1[i]分别與s2[j-1](j=1,2,...,len2)進行比較,若字元相等ci=左上角數值+1,且bi=1;若不相等,則ci等于左側或者上側重最大的一個數值,若左側和上側相等,則取左側,且bi=2或3(當取左側為2,取上側為3)。最後的c[][]和b[][]如下所示:
下表是c[][]:
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
A | ||||||
B | ||||||
C | ||||||
D | ||||||
下表是b[][]:
7 |
根據c[][]可以得出,LCS的長度為4(也就是c[][]最後一個值)。然後開始判斷内容是什麼,這是要根據b[][]來。
首先,b7=2,向左找b7=1,是以向左上角找b6,得到字母為s1[6]=[B];
b6=3,向上找b5=1,向左上角找b4,得到字母s1[4]=[D];
b4=2,向左找b4[1],得到字母s1[3]=[A];
b3=3,向上找b2=1,向左上角找b1,得到字母s1[1]=[B].
由于b1=0,是以算法停止,傳回結果為“BADB”。
代碼示範
void LCSL()
{
int i, j;
for(i=1;i<len1;i++)
for (j = 1; j < len2; j++)
{
if (s1[i - 1] == s2[j - 1])
{
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else
{
if (c[i][j - 1] >= c[i - 1][j])
{
c[i][j] = c[i][j - 1];
b[i][j] = 2;
}
else
{
c[i][j] = c[i - 1][j];
b[i][j] = 3;
}
}
}
}
void print(int i, int j)
{
if (i == 0 || j == 0)
return;
if (b[i][j] == 1)
{
print(i - 1, j - 1);
cout << s1[i - 1];
}
else if (b[i][j] == 2)
print(i, j - 1);
else
print(i - 1, j);
}