c++ - 如何在大字符串上应用最长公共(public)子序列算法？

Question

如何在更大的字符串(600000 个字符)上应用最长的公共(public)子序列。有没有办法在DP中做到这一点？我已经为较短的字符串做了这个。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

int dp[1005][1005];
char a[1005], b[1005];

int lcs(int x,int y)
{
    if(x==strlen(a)||y==strlen(b))
        return 0;
    if(dp[x][y]!=-1)
        return dp[x][y];
    else if(a[x]==b[y])
        dp[x][y]=1+lcs(x+1,y+1);
    else
        dp[x][y]=max(lcs(x+1,y),lcs(x,y+1));
    return dp[x][y];
}

int main()
{
    while(gets(a)&&gets(b))
    {
        memset(dp,-1,sizeof(dp));
        int ret=lcs(0,0);
        printf("%d\n",ret);
    }
}

Answer 1

你应该看看这个 article其中讨论了各种设计和实现注意事项。指出可以看Hirschberg's algorithm使用编辑距离(或 Levenshtein 距离)找到两个字符串之间的最佳对齐方式。它可以简化代表您所需的空间量。

在底部，您会发现“节省空间的 LCS”被定义为一种混合/伪代码，其中 m 是 A 和 的长度n 是 B 的长度:

int lcs_length(char *A, char *B) {
  // Allocate storage for one-dimensional arrays X and Y.

  for (int i = m; i >= 0; i--) {
    for (int j = n; j >= 0; j--) {
      if (A[i] == '\0' || B[j] == '\0') {
        X[j] = 0;
      }
      else if (A[i] == B[j]) {
        X[j] = 1 + Y[j+1];
      }
      else {
        X[j] = max(Y[j], X[j+1]);
      }
    }

    // Copy contents of X into Y. Note that the "=" operator here
    // might not do what you expect. If Y and X are pointers then
    // it will assign the address and not copy the contents, so in
    // that case you'd do a memcpy. But they could be a custom
    // data type with an overridden "=" operator.
    Y = X;
  }

  return X[0];
}

如有兴趣here is a paper关于大字母字符串上的 LCS。在 3.2 节中查找算法 Approx2LCS。