最长公共子序列
基本算法描述
最长公共子序列（LCS）问题是一种经典的动态规划（DP）问题。
假设两个序列为 s1 和 s2 （假设下标从 0 开始），原先我们的算法是用 f[i][j] 表示 s1[1..i] 和 s2[1..j] 的最长公共子序列长度。
那么，我们可以得到状态转移方程：
f[i][j] = max{f[i-1][j], f[i][j-1]) (i>0 && j>0 && s1[i] != s2[j])
f[i][j] = max{f[i-1][j], f[i][j-1], f[i-1][j-1] + 1} (i>0 && j>0 && s1[i] == s2[j])
f[i][j] = 0 (i==0 || j==0)
递推即可得到答案。
算法分析
假设两个序列长度分别为 n 和 m ，则原算法的时间复杂度显然可见是 O(n·m) 的。
空间复杂度上由于开了一个 f[0..n][0..m] 的数组，所以复杂度也是 O(n·m) 的。
当然，由于每一维度的 f 数组只和上一维度有关，所以空间复杂度可以压缩到 O(m) 。(此处的分析有误，在下一文中对空间压缩的方法给出了具体讨论)
一种新思路
算法描述
定义一种阈值数组 T[0..n][0..n]，T[i][k] 表示在序列 s2 中匹配 s1[1..i]，寻找到 k 项匹配的最小下标值。
换句话说，即满足 s1[1..i] 和 s2[1..j] 有 k 项匹配的最小 j 值。
e.g.:
s1 = “abcbdda”
s2 = “badbabd”
则 T[5,1] 表示在 s2 中找到能与 s1[1..5] 公共子序列长度为1的最小下标。显然第一个即可满足，所以 T[5,1] = 1 。
同理，T[5,2] = 3，T[5,3] = 6，T[5,4] = 7，T[5,5] = ∞ 。
显然，数组 T 在第二维上是递增的。且 T[i][k-1] < T[i+1][k] ≤ T[i][k] 。
则可得递推方程：
T[i+1][k] = min{j} (s1[i+1]==s2[j] && T[i][k-1] < j ≤ T[i][k])T[i+1][k] = T[i][k] (不存在上述条件的 j 时)
算法正确性在此不做证明。
据此我们找到最后一列中满足 T[n][k] != ∞ 的最大 k 值即为 LCS 答案。
对应的算法伪代码：
算法分析
此时的时间复杂度为O((n^2)log n)，空间复杂度一样是可以压缩到 O(n)。
算法改进
改进思路
建立一个匹配表，事先将 s1 数组中的元素去和 s2 进行匹配，得到匹配表。
e.g.:
s1 = “abcbdda”
s2 = “badbabd”
则对应匹配表为：
MATCHLIST[1] = <5,2>
MATCHLIST[2] = <6,4,1>
MATCHLIST[3] = <>
MATCHLIST[4] = MATCHLIST[2]
MATCHLIST[5] = <7,3>
MATCHLIST[6] = MATCHLIST[5]
MATCHLIST[7] = MATCHLIST[1]
对应的算法伪代码：
算法分析
时间复杂度 O((r+n)log n) （ n 表示字符串长度，r 表示两个字符串间能匹配的次数），最坏复杂度为 O(n^2 log n)。
空间复杂度 O(r+n)。
具体分析如下：
Step 1：整理匹配表
可使用带序号的排序。时间复杂度 O(nlog n)，空间复杂度 O(n)。
Step 2：初始化
时间：O(n)
Step 3：比较和匹配
时间：O(n + rlog n)
Step 4: 倒序恢复最长子序列
时间：最坏 O(n)，空间：O(r)
论文来自
A Fast Algorithm for Computer Longest Common Subsequences
—— James W.Hunt (Stanford University) & Thomas G.Szymanski (Princeton University)