c++ - 如何优化最长公共(public)子序列的 O(m.n) 解决方案？

Question

给定两个字符串，长度为 x1 的字符串 X 和长度为 y1 的字符串 Y，找出两个字符串中从左到右(但不一定在连续 block 中)出现的最长字符序列。

e.g if X = ABCBDAB and Y = BDCABA, the LCS(X,Y) = {"BCBA","BDAB","BCAB"} and LCSlength is 4.

我使用了这个问题的标准解决方案:

if(X[i]=Y[j]) :1+LCS(i+1,j+1)
if(X[i]!=Y[j]) :LCS(i,j+1) or LCS(i+1,j), whichever is greater

然后我使用了内存，使它成为一个标准的 DP 问题。

    #include<iostream>
    #include<string>
    using namespace std;
    int LCS[1024][1024];

     int LCSlen(string &x, int x1, string &y, int y1){

        for(int i = 0; i <= x1; i++)
            LCS[i][y1] = 0;

        for(int j = 0; j <= y1; j++)
             LCS[x1][j] = 0;

        for(int i = x1 - 1; i >= 0; i--){

            for(int j = y1 - 1; j >= 0; j--){

                LCS[i][j] = LCS[i+1][j+1];

                if(x[i] == y[j])
                LCS[i][j]++;

                if(LCS[i][j+1] > LCS[i][j])
                LCS[i][j] = LCS[i][j+1];

                if(LCS[i+1][j] > LCS[i][j])
                LCS[i][j] = LCS[i+1][j];

            }
        }

    return LCS[0][0];
    } 

    int main()
    {
        string x;
        string y;
        cin >> x >> y;
        int x1 = x.length() , y1 = y.length();
        int ans = LCSlen( x, x1, y, y1);
        cout << ans << endl;
        return 0;
    }

正在运行 here ，我在SPOJ中使用的这个解决方案我遇到了超出时间限制和/或运行时错误。

目前仅接受了 14 个用户解决方案。有没有更聪明的技巧来降低这个问题的时间复杂度？

Answer 1

LCS 是一个经典的、经过深入研究的计算机科学问题，对于具有两个序列的情况，已知其下限为 O(n·m)。

此外，您的算法实现没有明显的效率错误，因此它应该尽可能快地运行(尽管使用动态大小的 2D 矩阵而不是占用 4 MiB 内存的超大矩阵可能是有益的，并且需要频繁的缓存失效(这是一个代价高昂的操作，因为它会导致从主内存到处理器缓存的传输，这比缓存内存访问慢几个数量级)。

在算法方面，为了降低理论界限，您需要利用输入结构的细节:例如，如果您重复搜索其中一个字符串，则可能需要构建一个需要一些处理的搜索索引时间，但会使实际搜索更快。它的两个经典变体是 suffix array和 suffix tree .

如果已知您的至少一个字符串非常短(< 64 个字符)，您可以使用 Myers’ bit vector algorithm ，执行速度更快。不幸的是，该算法的实现远非易事。存在 an implementation in the SeqAn library ，但使用库本身有一个陡峭的学习曲线。

(有趣的是，该算法在生物信息学中应用频繁，已被用于人类基因组计划的序列组装。)