我的问题很简单:是否有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 }
是的,您可以在线性时间内完成此操作。 一种方法是为模式和文本构建后缀树并计算它们的交集。 但是,如果不涉及后缀树或后缀数组,我无法想到这样做的方法。
这就是你要找的东西:
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:"<
希望能帮助到你!
以上就是c/c++开发分享最常见的连续子序列 – 算法相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/559683.html