問題介紹

LCS問題(longest common subsequence problem)指的是求解兩個字符串最長公共子序列問題。這里的子序列是可以不連續的。LCS問題廣泛地出現在計算生物學中（DNA序列、系統生成樹等等）。這里介紹如何解決LCS問題，以及算法的正確性證明和性能分析。

解決方案

假設需要求解串X,Y的LCS，其中|X|=n,|Y|=m,c[i][j]表示X[1…i]和Y[1…j]的LCS長度,z[1…k]表示X[1…i]和Y[1…j]的LCS,k=c[i][j]，則問題就是求解$c[n][m]和z[c[n][m]]$

樸素的想法是，按照問題的要求，我們可以得到串X的所有子串，共有$2^n$個，然后判斷該子串是否出現在串Y中，每次判斷都需要遍歷串Y，因此時間復雜度為$O(2^n?m)$，這顯然是我們不能接受的復雜度。

為了解決這個問題，我們需要得到該問題的一些性質：

定理:

$$ifX[i]==Y[j]:c[i][j]=c[i?1][j?1]+1$$

$$otherwise：c[i][j]=max(c[i?1][j],c[i][j?1])$$

引理1:如果X[i]==Y[j]，則$z[c[i][j]]=X[i]$

證明：如果$z[c[i][j]]=X[i]$，且X[i]==Y[j]，那么不妨將X[i]加入到LCS中，$c[i][j]$加一，因此$z[1..c[i][j]]$不是LCS，與條件矛盾，證畢。

引理2:如果X[i]==Y[j]，則X[i-1]和Y[j-1]的LCS是$z[1..c[i][j]?1]$

證明：X[i-1]和Y[j-1]的LCS不是$z[1..c[i][j]?1]$，則使用X[i-1]和Y[j-1]的LCS替換$z[1..c[i][j]?1]$后再加上X[i]會得到X[i]和Y[j]的一個更長的一個LCS，與條件矛盾，證畢。引理2這里展示了問題的最優子結構

引理3:如果兩個串的LCS包含兩個串的末尾元素X[i]和Y[j]，則這兩個元素相等

證明：如果X[i]不等于Y[j]，則在LCS中，X[i]對應Y[j’],j’<j，Y[j]對應X[i’],i’<i，這不符合公共子串保留原串順序的性質，矛盾。證畢。

當X[i]==Y[j]時，由引理1保證了此時的LCS是串X[i]對應串Y[j’],$j^{\prime }?j$，對于$j^{\prime }<j$的情況，我們不妨用$j$來替換$j^{\prime }$，這樣也不會對LCS的長度有什么影響，然后由引理2，$c[i][j]=c[i?1][j?1]+1$

對于第二個條件，因為X[i]$=$Y[j]，那么此時的LCS要么屬于$c[i?1][j]$，要么屬于$c[i][j?1]$。

假設都不屬于，那么此時的LCS一定包含了$c[i?1][j]$中沒有的元素X[i]和$c[i][j?1]$中沒有的元素Y[j]，由引理3，矛盾。

在證明了上述定理以后我們可以根據該式子計算LCS:

1. 遞歸法

int LCS(string& x, string &y,int n,int m)
{if(-1==n || -1==m) return 0;if(x[n]==y[m]) return LCS(x, y, n-1, m-1)+1;else return max(LCS(x, y, n-1, m), LCS(x, y, n, m-1));
}

性能分析

分析遞歸樹，最壞的情況是每次x[n]!=y[m]，那么會得到一個高度為n+m的二叉樹，時間復雜度為$O(2^{n+m})$，空間復雜度為$O(n+m)$

2. 備忘錄方法（記憶化搜索）

分析上面時間復雜度我們發現，在搜索過程中很多的子問題都是一模一樣的，也就是具有重疊子問題性質，因此我們不妨每計算出一個子問題的結果就進行一次記錄，后面再次需要求解結果的時候就不需要再計算，而是直接返回結果。

int LCS(string& x, string &y,int n,int m,int *c)
{if(-1==n || -1==m) return 0;if(c[n*y.size()+m]) return c[n*y.size()+m];int ret;if(x[n]==y[m]) ret = LCS(x, y, n-1, m-1, c)+1;else ret = max(LCS(x, y, n-1, m, c), LCS(x, y, n, m-1, c));return c[n*y.size()+m]=ret;
}int main()
{string X,Y;cout<<"請輸入字符串X:"; cin>>X;cout<<"請輸入字符串Y:"; cin>>Y;int* c = new int[X.size()*Y.size()+10]();cout<<"字符串X和Y的LCS的長度為"<<LCS(X, Y, X.size(), Y.size(), c)<<endl;delete c;return 0;
}

性能分析

我們可以把對結果是否已經計算出的判斷和返回答案的耗費記錄在調用該狀態答案的耗費上，把實際結果的計算記錄在該狀態中，則最壞情況下每種狀態都要計算出來，因此時間復雜度為$O(nm)$，空間復雜度為$O(nm)$

3. 自底向上計算（動態規劃法）

我們觀察計算的過程，如果我們對狀態空間按照從左向右從上向下進行求解，就可以計算出所有的答案

int LCS(string& x, string &y,int n,int m,int *c)
{for(int i=1; i<=x.size(); ++i){for(int j=1;j<=y.size(); ++j){if(x[i-1] == y[j-1])c[i*y.size()+j]=c[(i-1)*y.size()+j-1]+1;elsec[i*y.size()+j]=max(c[(i-1)*y.size()+j], c[(i)*y.size()+j-1]);}}return c[n*y.size()+m];
}

性能分析

時間復雜度$O(nm)$，因為訪問的是連續的內存空間，因此這里的$O(nm)$應該比上面小。空間復雜度$O(nm)$，如果使用滾動數組還能夠將空間復雜度降低為$O(min(n,m))$，如果不使用滾動數組，想要得到完整的LCS串需要在計算的時候設置指針，最后進行回溯。如果使用滾動數組，需要使用分治法得到LCS串。

回溯如圖：