最长公共子序列

子序列与子串

子序列：有序列中若干符号，按原相对次序构成。例如 Tsinghua中sina是它的子序列，computer中omutr是子序列。它不要求所选的字母连续，只要求是按原次序组成就好。

子串是字符串中的一部分称为子串。例如Tsinghua中hua是子串，而shua就不是它的子串。

公共子序列就是两个序列X和Y共同的子序列。

最长公共子序列问题描述

输入：X={x1，x2，x3…xm}，Y={y1,y2,y3,y4…yn}

输出：Z=X和Y最长公共子序列

求解思路

我们第一印象肯定是暴力法，把两个序列的所有子序列都枚举出来，一一比较。诚然，这是一个思路，不过一个序列可能的子序列组合有2^n种可能，还需要比较，这就让复杂度高达O（m*2^n）。

因此我们只能更改策略。

优化子结构

设序列X=<x1,…,xm>和Y=<y1,…,yn>的最长公共子序列是Z=<z1, …, zk>

有如下几个情况：

1.如果zk=xm=yn，那么此时<z1,…, zk-1>是<x1,…,xm-1>和<y1,…,yn-1>的最长公共子序列

2.如果xm！=yn，zk！=xm，那么<z1,…, zk>是<x1,…,xm-1>和<y1,…,yn>的最长公共子序列

3.如果xm！=yn，zk！=yn，那么<z1,…, zk>是<x1,…,xm>和<y1,…,yn-1>的最长公共子序列

就可以归纳为：

如果：xm=yn，那么到找<x1,…,xm-1>和<y1,…,yn-1>的最长公共子序列，在其尾部加上xm。

如果xm！=yn，找到找<x1,…,xm-1>和<y1,…,yn>的最长公共子序列，找<x1,…,xm>和<y1,…,yn-1>的最长公共子序列，取两者中较长的序列即可。

如果我们用c[i][j]表示xi和yj的最长子序列的长度，那么得到以下的递推公式：

重叠子问题

总共有θ(mn)个不同的子问题

举例说明

我们以两个字符串ABCB 和 BDCA来举例。

构造表格

根据公式：

i=0或者j=0时 c[i][j]=0，得到下面的表格。

现在求C[2][2],也就是B行A列对应的c值，现在i，j>0,而且xi！=yj，那么c[2][2]=max{c[2][1],c[1][2]}=0,可以看出是由左侧和上侧决定了此处的值。

在C[2][3]处，B=B，也就是xi=yj了，此时根据公式C[2][3]=C[1][2]+1=0+1=1。

在C[2][4]处，B！=C，C[2][4]=max{C[1][4],C[2][3]}=1

此后的内容均依据此填充得到表格如下：

根据最右下角的值，我们可以知道最长的LCS为2。

如何求得最优解？

我们在构造上述表格时，用另外的表格记录下变动信息。

从c[0][0]开始，逐步增大：

如果当前元素相等，输出元素，而且同时增大i和j；

如果当前元素不相等，那么优先向更大的C值处增大，如果下方和右方一样大，优先向右增大，如果向下或者右到达边界，则向未达到边界的端移动。

如果已经到达数组最右下角那么结束。

上述例子的增大步骤如下：

这样就可以输出最优解。