最长公共子序列问题实验报告（最长公共子序列）

大家好，我是小夏，我来为大家解答以上问题。最长公共子序列问题实验报告，最长公共子序列很多人还不知道，现在让我们一起来看看吧！

1、这里要说的这个算法利用了nlogn的最长上升子序列(LIS)的技巧：用f[k]表示长度为k的上升子序列最后一个数最小是多少。

2、 在最长公共上升子序列中，令f[i,j][k]表示A串前i个数字，B串前j个数字，长度为k的公共上升子序列中，最后一个数最小是多少。

3、 当A[i]=B[j]时，像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中，这需要线性的时间扫一遍f[i,j]；

4、 当A[i]<>B[j]时，我们需要合并f[i-1,j]和f[i,j-1]，使得对于每个k满足f[i,j][k]:=min{ f[i-1,j][k],f[i,j-1][k] }。这需要线性的时间扫一边f[i-1,j]和f[i,j-1]并取k相同时的较小值。

5、 最后输出f[n,m]的长度（使f[n,m][k]有意义的最大的k）。

6、 这样的复杂度是三方的，我们需要优化。

7、 考虑A[i]=B[j]的情况。当i固定时，随着j的增加，插入的位置一定也在后移，因为同样是插入的A[i]，但j的增加（B串长度的增加）使得f [i,j]更优，因此可以更新的值就更靠后。于是，对于每个i，我们可以按照k的顺序扫描f[i-1,j][k] 并在A[i]可以插入f[i-1][j]的k位置时增加j，从而预处理所有A[i]=B[j]时A[i]应该插入的位置。

8、 再考虑A[i]<>B[j]的情况。从定义看，f[i-1,j-1]和f[i-1,j]只有一个地方不一样，因为多一个数最多只能造成一个k 的值变小；同样地，f[i-1,j-1]和f[i,j-1]也只有一个地方不一样。因此，f[i-1,j]和f[i,j-1]最多只有两个k所对应的值不相同，且当有两个不同的值时，总是f[i-1,j]中的某个值较小，f[i,j-1]中的某个值较小。这给我们优化的余地。在每次处理完f[i,j]时，我们可以记录一个值x[i,j]表示f[i,j][k]与f[i-1,j][k]中值不一样的k是多少，在A[i]=B[j]时直接赋值为插入的位置，在 A[i]<>B[j]时待后文说明。以后合并时，先让f[i,j]:=f[i-1,j]（由于此时的f[i-1,j]已经没有别的用处了，因此可以用滚动数组记录，直接令f[i-1,j]是f[i,j]，避免实际的赋值操作），然后将新的f[i,j]中的，使f[i,j-1][k]比f[i- 1, j][k]小的k所对应值更新。这个k是多少呢？显然应该是x[i,j-1]。这样的操作同时可以确定x[i,j]=x[i,j-1]。

9、 这样，复杂度就达到了平方。

10、 附参考的资料（原来从这篇论文里学到的，不知道有没有此类的中文资料，估计没有才在这里写了一个，感兴趣的话可以下载附件仔细研究）

11、引自M67的博客： http://www.matrix67.com/blog/?s=LCIS

本文到此讲解完毕了，希望对大家有帮助。