c/c++语言开发共享最常见的连续子序列 – 算法

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

这就是你要找的东西：

KMP算法 c 实现

基本理论：

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

希望能帮助到你！