最长公共子序列问题（LCS）（生物信息学中常用算法）
子序列的概念：
设X=< x1, x2,┅, xm>，若有1≤i1< i2< ┅ <ik≤m，使得
Z=< z1, z2,┅, zk> = < xi1, xi2,┅, xik>，则称Z是X的子序列，
记为Z<X。
e.g. X=<A,B,C,B,D,A,B>, Z=<B,C,B,A>, 则有Z<X。
公共子序列的概念：
设X，Y是两个序列，且有Z<X和Z<Y，
则称Z是X和Y 的公共子序列。
最长公共子序列的概念：
若Z<X，Z<Y，且不存在比Z更长的X和Y 的公共子序列，
则称Z是X和Y 的最长公共子序列，记为ZLCS(X , Y)。
最长公共子序列往往不止一个。
e.g. X=<A,B,C,B,D,A,B>, Y=<B,D,C,A,B,A>, 则
Z=<B,C,B,A>, Z’=<B,C,A,B>, Z’’=<B,D,A,B>
均属于LCS(X , Y) ，即X,Y有3个LCS。
如何找出X和Y的一个最长公共子序列？
Brute-force法：列出X的所有长度不超过n（即Y）的子序列，
从长到短逐一进行检查，看其是否为Y的子序列，
直到找到第一个最长公共子序列。
由于X共有2m个子序列，故此方法对较大的m没有实用价值。
是否能使用动态规划法？如何用？
分析：
记Xi=﹤x1，…，xi﹥即X序列的前i个字符 (1≤i≤m)（前缀）
Yj=﹤y1，…，yj﹥即Y序列的前j个字符 (1≤j≤n)（前缀）
假定Z=﹤z1，…，zk﹥∈LCS(X , Y)。
若xm=yn（最后一个字符相同），则不难用反证法证明：
该字符必是X与Y的任一最长公共子序列Z（设长度为k）的
最后一个字符，即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)
即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。
若xm≠yn，则亦不难用反证法证明：
要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。
由于zk≠xm与zk≠yn其中至少有一个必成立，因此：
若zk≠xm则有Z∈LCS(Xm-1 , Y)，
若zk≠yn 则有Z∈LCS(X , Yn-1)。
∴若xm=yn，则问题化归成求Xm-1与Yn-1的LCS
（LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1）
若xm≠yn 则问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS
LCS(X , Y)的长度为：
max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}
求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度
这两个问题不是相互独立的：
∵两者都需要求LCS(Xm-1，Yn-1)的长度,
因而具有重叠性。
另外两个序列的LCS中包含了两个序列的前缀的LCS，
故问题具有最优子结构性质考虑用动态规划法。
引进一个二维数组C，用C[i,j]记录Xi与Yj的LCS的长度
如果我们是自底向上进行递推计算，那么在计算C[i,j]之前，
C[i-1,j-1], C[i-1,j]与C[i,j-1]均已计算出来。此时我们
根据X[i]=Y[j]还是X[i]Y[j]，就可以计算出C[i,j]：
若X[i]=Y[j]，则执行C[i,j]←C[i-1,j-1]+1；若X[i]Y[j]，则根据：
若C[i-1,j]≥C[i,j-1]则C[i,j]取C[i-1,j]；否则C[i,j]取C[i,j-1]。即有
C[i,j]=
e.g. 如下图：
0 1 2 3 4 5 6
yj B D C A B A
0 xi 0 0 0 0 0 0 0
↑ ↑ ↑↖ ↖
1 A 0 ←0 ←0←0 1←1 1
↖ ↑↖
2 B 0 1 ←1←1 ←1 2 ←2
↑ ↑↖ ↑ ↑
3 C 0 1 ←1 2 ←2←2 ←2
↖ ↑ ↑ ↑↖
4 B 0 1 ←1 2 ←2 3 ←3
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2←2 ←2 3 ←3
↑ ↑ ↑↖ ↑↖
6 A 0 1 2←2 3←3 4
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2←2 3 4 ←4
为了构造出LCS，使用一个mn的二维数组b，
b[i,j]记录C[i,j]是通过哪一个子问题的值求得的,
以决定搜索的方向：
若C[i-1,j]≥C[i,j-1]，则b[i,j]中记入“↑”；
若C[i-1,j] < C[i,j-1]，则b[i,j]中记入“←”；
算法 LCS_L(X,Y,m,n,C)
for i=0 to m do C[i,0]←0
for j=1 to n do C[0,j]←0
for i=1 to m do {
for j=1 to n do{
if x[i]=y[j] then {C[i,j]←C[i-1,j-1]+1；
b[i,j]←“↖” ；}
}el if C[i-1,j]≥C[i,j-1] then {C[i,j]←C[i-1,j]；
b[i,j]←“↑” ；}
}el{C[i,j]←C[i,j-1]；
b[i,j]←“←” ；}
算法的时间复杂度显然是(m×n)的。
输出一个LCS(X,Y)的递归算法：
LCS_Output(b,X,i,j)
If i=0 or j=0 then return;
If b[i,j]=“↖”then /*X[i]=Y[j]*/
{LCS_Output(b,X,i-1,j-1)；
输出X[i]；}
el if b[i,j]=“↑”then /*C[i-1,j]≥C[i,j-1]*/
LCS_Output(b,X,i-1,j)
el if b[i,j]=“←” then /*C[i-1,j]<C[i,j-1]*/
LCS_Output(b,X,i,j-1)
e.g. 对上述例子调用LCS_Output(b,X,7,6)。
算法分析：
由于每次调用至少向上或向左（或向上向左同时）移动一步，
故最多调用（m+n）次就会遇到i=0或j=0的情况，
此时开始返回。返回时与递归调用时方向相反，步数相同，
故算法时间复杂度为(m＋n)。
注意：仅用“↑” ，“←” ，“↖”是搜索不到所有的LCS的；
主要是由于在上述LCS_L算法里，
对于语句if C[i-1] ≥ C[i,j-1] then ….，
没有区分C[i-1,j]＞C[i,j-1] 和C[i-1,j]＝C[i,j-1]
这两种不同的情况。因此，要找出所有的LCS，
当满足X[i]Y[j]且C[i-1,j]＝C[i,j-1]时，要执行b[i,j]←“←↑”，
即记录两个搜索方向，才能够据此找出所有的LCS。
为节省空间，数组b亦可不用，直接
根据X[i]=Y[j]还是X[i]Y[j]以及C[i,j-1]，C[i-1,j]来找出搜索方向：
X[i]=Y[j]等价于b[i,j]=“↖”，
X[i]Y[j]且C[i,j-1] > C[i-1,j] 等价于b[i,j]=“←”，
X[i]Y[j]且C[i,j-1] < C[i-1,j] 等价于b[i,j]=“↑”，
X[i]Y[j]且C[i,j-1] = C[i-1,j] 等价于b[i,j]=“←↑”，
不用b数组可节省(m×n)的空间，但算法写起来稍烦一些。
执行时间的量级两者相同。
如果只需计算LCS的长度而无需求出具体的LCS，
