c++ - 最长公共连续子序列 - 算法

Question

我的问题很简单：是否有一个 O(n) 算法可以找到两个序列 A 和 B 之间最长的连续子序列？我搜索了它，但所有结果都是关于 LCS 问题的，这不是我想要的。

注意：如果您愿意提供任何示例代码，我们非常欢迎您这样做，但如果可以，请使用 C 或 C++。

编辑：这是一个例子：

A: { a, b, a, b, b, b, a }
B: { a, d, b, b, b, c, n }
longest common contiguous subsequence: { b, b, b }

score 2 · Accepted Answer

是的，你可以在线性时间内做到这一点。一种方法是为模式和文本构建后缀树并计算它们的交集。不过，我想不出一种不涉及后缀树或后缀数组的方法。

score 0 · Accepted Answer

这就是你要找的：

KMP算法 c 实现

基本理论：

score 0 · Accepted Answer

我不确定是否存在 O(n) 算法。这是一个 O(n*n) 的动态解决方案，也许对你有帮助。令 lcs_con[i][j] 表示以数组 A 中的元素 A_i 和数组 B 中的元素 B_j 结尾的最长公共连续子序列。然后我们可以得到以下等式：

lcs_con[i][j]=0 if i==0 or j==0
lcs_con[i][j]=0 if A_i != B_j
lcs_con[i][j]=lcs_con[i-1][j-1] if A_i==B_j

我们可以在计算过程中记录lcs_con[i][j]的最大值和结束索引，得到最长的公共连续子序列。代码如下：

#include<iostream>

using namespace std;


int main()
{
    char A[7]={'a','b','a','b','b','b','a'};
    char B[7]={'a','d','b','b','b','c','n'};

    int lcs_con[8][8];    
    memset(lcs_con,0,8*8*sizeof(int));

    int result=-1;
    int x=-1;
    int y=-1;

    for(int i=1;i<=7;++i)
      for(int j=1;j<=7;++j)
      {
          if(A[i-1]==B[j-1])lcs_con[i][j]=lcs_con[i-1][j-1]+1;
          else lcs_con[i][j]=0;

          if(lcs_con[i][j]>result)
          {
               result=lcs_con[i][j];
               x=i;
               y=j;                   
          }
      }

   if(result==-1)cout<<"There are no common contiguous subsequence";
   else
   {
       cout<<"The longest common contiguous subsequence is:"<<endl;
       for(int i=x-result;i<x;i++)cout<<A[i];
       cout<<endl;
   }

   getchar();
   getchar();

   return 0;    
}

希望能帮助到你！

c++ - 最长公共连续子序列 - 算法

3 回答 3

Related

Reference