LCS(最長公共子序列)
百度百科：
一個序列 S ，如果分別是兩個或多個已知序列的子序列，
且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
在這裡我們要注意的是，S在已知序列中可以不連續。
比如ABCBDAB和BDCABA的LCS為BCBA，BCBA在原序列中並不連續出現。
LCS通常利用動態規劃算法求解，最簡單的求解方式如《算法導論》所述：
1.設輸入為X1X2…Xm，Y1Y2…Yn，構造二維數組B、C；
其中B[i][j]存儲C[i][j]的最優解指向，C[i][j]存儲X[1…i]和Y[1…j]的LCS長度；
2.B、C數組同時更新：
2.1.令B[0][k]、C[0][k]（k=0…n）和B[k][0]、C[k][0]（k=0…m）為0；
2.2.按下標從小到大的順序依次計算每行的B[i][j]和C[i][j]，規則如下：
①.若X[i]=Y[j]，則C[i][j]=C[i-1][j-1]+1，B[i][j]=0；
②.若X[i]！=Y[j]，則C[i][j]=Max(C[i][j-1],C[i-1][j])，B[i][j]=1或2；
3.更新完B、C後，從C[m][n]開始遞歸輸出，根據B[i][j]的指向打印LCS；
相信大家都明白這個原理，簡單的用一張圖來說明一下：
1.箭頭代表B[i][j]的值，其中用指向左上方的箭頭代表0，←和↑代表1和2(或2和1)；
2.箭頭下方的數字為C[i][j]的值，即子問題X[1…i]和Y[1…j]的LCS長度；
可是這樣的構造只能輸出一個LCS，但是我們發現BCBA、BCAB、BDAB都是該序列集的LCS。
為什麼呢？因為該算法在C[i-1][j]=C[i][j-1]時，只記錄了一種情況！即沒有保存分支！
如何簡單的修改算法，以求得多個LCS呢？下面介紹一種改進的方法。
還是利用數組B、C，並且C的計算規則不變，下面修改B的計算規則：
1.若X[i]=Y[j]，B[i][j]=0；
2.若X[i]!=Y[j]，有以下判斷：
①.若C[i-1][j]>C[i][j-1]，則C[i][j]=C[i-1][j]，B[i][j]=1；
②.若C[i-1][j]<C[i][j-1]，則C[i][j]=C[i][j-1]，B[i][j]=2；
③.若C[i-1][j]=C[i][j-1]，則C[i][j]的長度任取，B[i][j]=3；
此時用另一張圖表示該算法：
1.用四種箭頭表示B[i][j]的值，其中←和↑都存在時，表示C[i-1][j]=C[i][j-1]；
2.輸出的時候采用正則表達式的思想：遇到B[i][j]=3時，同時對兩種情況進行遞歸；
形式為“（←+↑）”，其中←和↑分別表示兩個子問題的LCS；
補充：（A+B），在正則表達式中意義為A或B，即“+”表示二選一的關系。
下面給出C++源代碼幫助大家更好地理解：（編譯器為Codeblocks）
1 #include<iostream>
2 #include<string.h>
3 #define M 100
4 #define N 100
5 using namespace std;
6
7 void LCS_length(string x,string y,int B[M][N],int C[M][N])/*動態規劃*/
8 { for(int i=1;i<=x.length()-1;i++) C[i][0]=0;
9 for(int j=0;j<=y.length()-1;j++) C[0][j]=0;
10 for(int i=1;i<=x.length()-1;i++)
11 for(int j=1;j<=y.length()-1;j++)
12 { if(x[i]==y[j])
13 { C[i][j]=C[i-1][j-1]+1;B[i][j]=0/*Up&Left*/;}
14 else if(C[i-1][j]>C[i][j-1])
15 { C[i][j]=C[i-1][j];B[i][j]=1/*Up*/;}
16 else if(C[i-1][j]<C[i][j-1])
17 { C[i][j]=C[i][j-1];B[i][j]=2/*Left*/;}
18 else
19 { C[i][j]=C[i][j-1];B[i][j]=3/*Up+Left*/;}}}
20
21 void Print_LCS(string x,int B[M][N],int i,int j)/*輸出LCS*/
22 { if(!i||!j) return;
23 if(!B[i][j])
24 { Print_LCS(x,B,i-1,j-1);cout<<x[i];}
25 else if(B[i][j]==1)
26 Print_LCS(x,B,i-1,j);
27 else if(B[i][j]==2)
28 Print_LCS(x,B,i,j-1);
29 else
30 { cout<<'(';
31 Print_LCS(x,B,i-1,j);
32 cout<<'+';
33 Print_LCS(x,B,i,j-1);
34 cout<<')';}}
35
36 int main()
37 { string x,y;
38 cin>>x;cin>>y;
39 x=' '+x;y=' '+y;
40 int B[M][N],C[M][N];
41 LCS_length(x,y,B,C);cout<<endl;
42 Print_LCS(x,B,x.length(),y.length());}
看完Print_LCS()函數，大家應該大致有所了解，下面給出運行結果：
輸入為ABCBDAB、BDCABA；
輸出為(BCBA+(BC+BD)AB)，即表示BCBA、BCAB、BDAB都為輸入的LCS；
當然，如果不想采用這種形式，也可以：
1.用字符型數組（如Vector）或String型變量保存輸出；
2.根據括號分解，輸出多個LCS；
還有一種方式：
1.遍歷數組B，用棧保存B[i][j]=3的點的坐標，比如[7，6]，[5，3]等；
2.讓這些點的賦值從11……11逐漸變為22……22；
因為B[i][j]=3可以理解為B[i][j]=1或2，那麼用二進制序列的思想遍歷每種賦值情況；
當然此時時間開銷更大，還可能重復輸出，所以建議第一種方式。
