最长公共子序列（LCS）问题算法详解+例题（转换成LIS，优化为O(nlogn)，看不懂你来打我）

最长公共子序列（LCS）问题

给出两个⻓度为n的序列$\{a_i\}和\{b_i\}${ai​}和{bi​}，求它们的公共子序列的最⻓⻓ 度。 例如两个序列分别为$(1,2,4,8,16)$(1,2,4,8,16)和$(2,4,6,8,10)$(2,4,6,8,10)，那么它们的$LCS$LCS就是$(2,4,8)$(2,4,8)。

由于子序列是按照从前往后的顺序，我们自然而然地可以将这两个序列 的前缀序列的LCS问题作为子问题。

1.朴素做法 $O(n^2)$O(n2)

设$f(i,j)$f(i,j) 为 $a$a 序列的前 $i$i个数字，和 $b$b 序列的前 $j$j 个数字，的$LCS$LCS。那 么分别考虑最后两个数字的情况：

▶ 如果相同，则加入$LCS$LCS中，并计算$f(i−1,j−1)；$f(i−1,j−1)；

▶ 如果不同，则寻找退路，在$f(i−1,j)$f(i−1,j)和$f(i,j−1)$f(i,j−1)中取较大的。 复杂度$O(n^2)$O(n2)。

那么看一下这个模板题：

50%的数据 $n<=10^3$n<=103

根据上面分析的朴素做法代码如下：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=100007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,a[N],b[N],f[100005][10005];
void naive()//（太天真了）
{
    over(i,1,n)
    over(j,1,n)
    {
        if(a[i]==b[j])
            f[i][j]=f[i-1][j-1]+1;
        else f[i][j]=max(f[i-1][j],f[i][j-1]);
    }
    printf("%lld\n",f[n][n]);
}
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
        scanf("%lld",&a[i]);
    over(i,1,n)
        scanf("%lld",&b[i]);
    naive();
    return 0;
}

果不其然过了50%的点，只拿了50分。

朴素做法还是太天真了，但是有一系列的题只要求你用朴素做法

要是想拿满分，就必须要优化到$O(nlogn)$O(nlogn)才行

2.转换成LIS优化$O(nlogn)$O(nlogn)

如果a和b都各自满足数字互不相同的性质，那么解法可以得到进一步优化。

首先将a和b中的数字进行离散化，并去除只在一个序列中出现的数 字。那么对于剩下的a中的每个数字，它在b中某个位置对应出现，于 是问题就变成了：选取尽可能多的a，使得它们在b中对应的出现顺序 单调递增。
也就是一个$LIS$LIS（最长上升子序列）问题。 从而可以在$O(nlogn)$O(nlogn)的复杂度进行解决。

没看懂？没事，下面给出一个大佬的解释

关于为什么可以转化成$LIS$LIS问题

$A:3 2 1 4 5$A:32145
$B:1 2 3 4 5$B:12345
我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：
$A: a b c d e$A:abcde
$B: c b a d e$B:cbade
这样标号之后，$LCS$LCS长度显然不会改变。但是出现了一个性质：
两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。
换句话说，只要这个子序列在B中单调递增，它就是A的子序列。
哪个最长呢？当然是B的$LIS$LIS最长。
自此完成转化。

很清晰对吧，那么我们就可以把LCS问题转换成LIS问题来用$O(nlogn)$O(nlogn)求解了。什么，你还不会LIS（最长上升子序列）？快点开[这个链接学习一下
https://blog.csdn.net/weixin_45697774/article/details/105465483

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=100007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,a[N],b[N],tree[N],mp[N];

inline void update(ll k,ll val)//树状数组维护的是mp数组的值的最大值
{
    while(k<=N)
    {
        tree[k]=max(tree[k],val);
        k+=k&(-k);
    }
}
inline ll query(ll k)//查到的k都是值小于k的节点的最大值，所以就保证了单调性
{
    ll res=0;
    while(k)
    {
        res=max(res,tree[k]);
        k-=k&(-k);
    }
    return res;
}

void advanced()
{
    over(i,1,n)
        mp[b[i]]=i;//mp函数就是一个简单的映射离散化
    over(i,1,n)//如果a里有b里没有那么p[a[i]]就是0，树状数组是没办法处理0的所以就不会任何影响
        update(mp[a[i]],query(mp[a[i]])+1);
    printf("%lld\n",query(n));
}
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
        scanf("%lld",&a[i]);
    over(i,1,n)
        scanf("%lld",&b[i]);
    advanced();
    return 0;
}

3.P2758 编辑距离

P2758 编辑距离

类似$LCS$LCS来定义状态：设f(i,j)表示$A[1...i]和B[1...j]$A[1...i]和B[1...j]的编辑距离。

由于编辑之后最后一个字符一定要相同，我们就分情况讨论：

▶ 如果$A[i] = B[j]$A[i]=B[j]，则$f(i,j) = f(i−1,j−1)$f(i,j)=f(i−1,j−1)

▶ 否则，我们有三种不同的操作方法：

1. 将$A[i]$A[i]删除，转化为$f(i−1,j)$f(i−1,j)
2. 将$B[j]$B[j]插入到最后，转化为$f(i,j−1) $
3. 将$A[i]$A[i]修改为$B[j]$B[j]，转化为$f(i−1,j−1)$f(i−1,j−1)

注意边界条件：$f(0,i) = f(i,0) = i$f(0,i)=f(i,0)=i

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=2007;
const ll INF=1e10+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;
ll n,m,f[N][N];
char a[N],b[N];
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1),m=strlen(b+1);
    over(i,1,N-1)//必须-1，f数组总共就从0-(N-1),就是搞不明白为什么这里写错答案会不一样
        f[0][i]=f[i][0]=i;
    over(i,1,n)over(j,1,m)
    {
        if(a[i]==b[j])
            f[i][j]=f[i-1][j-1];//不用改
        else f[i][j]=min(min(f[i-1][j]+1,//删掉a
                            f[i][j-1]+1),//删掉b
                          f[i-1][j-1]+1);//把a改成b
    }
    printf("%lld\n",f[n][m]);
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧