最长公共上升子序列的另一个O(mn)的算法

Matrix67's profileMatrix67's SpaceBlogLists

Tools

Help

< Previous Next >

October 18

最长公共上升子序列的另一个O(mn)的算法

我在这个帖子里说过nlogn求最长上升子序列的方法：
http://www.oibh.org/bbs/viewthread.php?tid=10682

下面引用我自己的发言：

    f表示长度为i的上升子序列最后一个数最小是多少。显然数组f是单增的。

    读到一个新的数x后，找到某个i使得x>f[i]且x<=f[i+1]，于是用x去更新f[i+1]；特别地，如果所有的f[i]都小于x，则增加f的长度。
    最后看f数组有多长就行了。

    由于f单增，所以查找i时可以用二分查找，因此时间复杂度为O(nlogn)。

    举个例子，假如序列为 3 2 8 6 7 4 5 7 3，则f数组的变化过程如下：
    3
    2
    2 8
    2 6
    2 6 7
    2 4 7
    2 4 5
    2 4 5 7
    2 3 5 7
    最后，f的长度达到4，因此答案为4。

    注意，最后的f数组不一定是最长上升子序列的一个方案。

这里要说的这个算法利用了nlogn的最长上升子序列(LIS)的技巧：用f[k]表示长度为k的上升子序列最后一个数最小是多少。
在最长公共上升子序列中，令f[i,j][k]表示A串前i个数字，B串前j个数字，长度为k的公共上升子序列中，最后一个数最小是多少。

    当A[i]=B[j]时，像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中，这需要线性的时间扫一遍f[i,j]；
    当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相同时的较小值。
    最后输出f[n,m]的长度（使f[n,m][k]有意义的最大的k）。

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

考虑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]应该插入的位置。
再考虑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]。

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

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

Matrix67原创

转载请注明出处

3:36 PM | Blog it | Program Impossible