logn的最长公共子序列

最新推荐文章于 2024-04-29 21:11:51 发布

HumveeA6

最新推荐文章于 2024-04-29 21:11:51 发布

阅读量431

点赞数

分类专栏：动态规划模板字符串

本文链接：https://blog.csdn.net/HumveeA6/article/details/79794974

版权

本文介绍了如何使用O(nlogn)时间复杂度的算法求解最长公共子序列（LCS），该算法源于James W. Hunt和Thomas G. Szymansky的论文。通过构建新序列并找到最长严格递增子序列，可以得到原序列的LCS。以A={a,b,c,d,b}和B={b,c,a,b}为例，展示了算法的具体应用和实现。" 52912294,5078909,使用C++在DEV C++中连接MySQL数据库,"['C语言', '数据库', 'MySQL连接']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

最长公共子序列（LCS）最常见的算法是时间复杂度为O(n^2)的动态规划(DP)算法，但在James W. Hunt和Thomas G. Szymansky 的论文”A Fast Algorithm for Computing Longest Common Subsequence”中，给出了O(nlogn)下限的一种算法。
定理：设序列A长度为n，{A(i)}，序列B长度为m，{B(i)}，考虑A中所有元素在B中的序号，即A某元素在B的序号为{Pk1,Pk2,..}，将这些序号按照降序排列，然后按照A中的顺序得到一个新序列，此新序列的最长严格递增子序列即对应为A、B的最长公共子序列。
举例来说，A={a,b,c,d,b}，B={b,c,a,b}，则a对应在B的序号为2，b对应序号为{3,0}，c对应序号为1，d对应为空集，生成的新序列为{2,3, 0, 1, 3, 0}，其最长严格递增子序列为{0,1,3}，对应的公共子序列为{b, c, b}

实现代码：（洛谷P1439）：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int N=1000005;
vector<int>v[N],a,d;
int main()
{
    int n,i,j,A[N],B[N];
    cin>>n;
    for(i=1;i<=n;i++)scanf

最低0.47元/天解锁文章