最常见的连续子序列 – 算法

我的问题很简单：是否有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 } 

Answer 1

是的，您可以在线性时间内完成此操作。 一种方法是为模式和文本构建后缀树并计算它们的交集。 但是，如果不涉及后缀树或后缀数组，我无法想到这样做的方法。

Answer 2

这就是你要找的东西：

KMP算法 c 实现

基本理论：

1. 如何使用C ++找到最长公共子串

2. http://en.wikipedia.org/wiki/Longest_common_substring_problem

Answer 3

我不确定是否存在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 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:"< 

希望能帮助到你！