最长公共子序列

nikangle · 2023-10-09 14:45:48 · 算法·理论

定义

1. 子序列：对于一个长度为 n 的序列 A 的长度为 k 的下标序列 v_1,v_2, \dots ,v_k(1 \le v_1 < v_2 < \dots < v_k \le n)，称称序列 A_{v_1},A_{v_2}, \dots ,A_{v_k} 为序列 A 的子序列。序列 A 共有 2^n 个子序列（k 可以等于 0）。

2. 公共子序列：若长度为 n 序列 A 的一个子序列与长度为 m 的序列 B 的一个子序列相同（长度相同，且每一位都相同）则称该子序列为序列 A 与序列 B 的公共子序列，该子序列长度为该公共子序列长度。

3. 最长公共子序列（\text{LCS}）：在两个序列 A 和 B 中，长度最大的公共子序列的长度就是 A 与 B 的最长公共子序列的长度，长度为最长公共子序列长度的所有公共子序列都是 A 和 B 的最长公共子序列。

基础题型

给定序列 A 和 B，求他们最长公共子序列的长度。

例题：P1439

朴素求法

用 dp_{i,j} 表示序列 A 的前 i 位与序列 B 的前 j 位的最长公共子序列的长度。

考虑转移：

当 A_i = B_j 时，最长公共子序列长度可以增加，即 dp_{i,j} = dp_{i-1,j-1} + 1。

否则，长度无法更新，dp_{i,j} = \max(dp_{i-1,j},dp_{i,j-1})。

此做法复杂度为 \mathcal O(n^2)，空间复杂度为 \mathcal O(n^2) 或用滚动数组优化为 \mathcal O(n)。能得到 \text{50} 分。

Code

for(int i=0;i<=n;i++){
    dp[i][0]=dp[0][i]=0;
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(a[i]==b[j]){
            dp[i][j]=dp[i-1][j-1]+1;
        }
        else{
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
}
cout<<dp[n][n];

优化(仅对于此题可行)

题目中说序列 A 与序列 B 都是 1 \sim n 的排列，可以记录每一个数在 A 序列中出现的位置 numa_i 和每一个数在 B 序列中出现的位置 numb_i（无重复），然后对于每一个 A_i，只要找出序列 B 的前 numb_{A_i}-1 位与序列 A 的前 i-1 位的最长公共子序列，再加一，就是序列 A 的前 i 位与序列 B 的前 numb_{A_i} 位的最长公共子序列长度。

用 dp_i 表示在 B 序列的前 i 位和 A 序列的前 numa_{B_i} 的最长公共子序列长度。

从前到后遍历序列 A，每一步求出 dp_{numb_{A_i}}，即求出 \max(dp_1,dp_2, \dots ,dp_{numb_{A_i}-1})，因为 A 序列是顺序遍历的，所以顺序不会错乱，答案正确。

可使用数据结构维护，下给出树状数组维护的模板。

时间复杂度 \mathcal O(n \log n)，空间复杂度 \mathcal O(n)，能够 \text{AC}。

Code

int lowbit(int x){
    return x&(-x);
}
int getmax(int x){
    int ans=0;
    for(;x>0;x-=lowbit(x)){
        ans=max(ans,cal[x]);
    }
}
void modify(int x,int d){
    for(;x<=n;x+=lowbit(x)){
        cal[x]=max(cal[x],d);
    }
}
int main(){
    for(int i=1;i<=n;i++){
        numa[a[i]]=i;//虽然用不到
        numb[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
        dp[numb[a[i]]]=getmax(numb[a[i]]-1)+1;
        modify(numb[a[i]],dp[numb[a[i]]]);
    }
}

进阶题型 1

求最长公共子序列的方案数。

例题：洛谷 P2516

可以在 DP 的过程中维护方案数：记录 sum_{i,j} 表示序列 A 的前 i 位与序列 B 的前 j 位构成最长公共子序列有 sum_{i,j} 种方案。