P12713 [KOI 2021 Round 1] 公共子序列扩展题解

· · 题解

我们不难发现，在一个序列中，可能会有很多个位置不同但是最后内容相同的子序列。

举个例子：

acbcbcbc
cbc

如上图，第一个字符串是原序列，第二个字符串是第一个字符串的子序列。

子序列可能是原序列第 2 个、第 3 个和第 4 个位置组成的，也可能是原序列第 2 个、第 5 个和第 6 个位置组成的，还可能是原序列第 4 个、第 5 个和第 6 个位置组成的等，有很多。

本题的大致意思就是说，给你两个字符串 a 和 b 和它们的一个公共子序列 w，问能否在 w 任意一个位置插入一个字符，使 w 依然是 a 和 b 的公共子序列。

思路

我们需要先分别预处理出使 w 最后能完整的放到字符串 a 或 b，且 w 的每个字符放入 a 和 b 最左边的位置和最右边的位置。（这里的放实际上就是将字符串 w 的每一位分别放入 a 或 b，是最后能把 w 全部放入）

如果我们想要在 w 的第 i 个位置和第 i+1 个位置之间插入一种字符，那么我们需要分别计算出 w 的第 i 个字符放入字符串 a 的最左面的位置、w 的第 i+1 个字符放入字符串 a 的最右面的位置，最后我们再统计这个区间这种字符的数量有多少个，对于字符串 b 也同理，如果 a 中这种字符在这个区间的数量和 b 中这种字符在这个区间的数量都大于 0，则 w 是可扩展的，输出 1，否则输出 0。

实现

我们先枚举 w 字符串每一个位置，紧接着再枚举每个字母，按照刚才说的的方法写就可以，统计 a 和 b 某一个区间的某一种字符数量可以用前缀和解决。

本题不太好写，可以参考本蒟蒻的代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+10,M=26;
int n,m,t,sum1[N][M],sum2[N][M],l1[N],r1[N],l2[N],r2[N],T;
char a[N],b[N],w[N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s%s%s",a+1,b+1,w+1);
        n=strlen(a+1);
        t=strlen(b+1);
        m=strlen(w+1);
        for(int i=1;i<=n;i++){
            for(int j=0;j<=25;j++){
                if(j==a[i]-'a') sum1[i][j]=sum1[i-1][j]+1;
                else sum1[i][j]=sum1[i-1][j];
            }
        }
        for(int i=1;i<=t;i++){
            for(int j=0;j<=25;j++){
                if(j==b[i]-'a') sum2[i][j]=sum2[i-1][j]+1;
                else sum2[i][j]=sum2[i-1][j];
            }
        }
        int p=1;
        for(int i=1;i<=n;i++){
            if(p>m) break;
            if(a[i]==w[p]) l1[p++]=i;
        }
        p=m;
        for(int i=n;i>=1;i--){
            if(p<1) break;
            if(a[i]==w[p]) r1[p--]=i;
        }
        p=1;
        for(int i=1;i<=t;i++){
            if(p>m) break;
            if(b[i]==w[p]) l2[p++]=i;
        }
        p=m;
        for(int i=t;i>=1;i--){
            if(p<1) break;
            if(b[i]==w[p]) r2[p--]=i;
        }
        bool flag=false;
        for(int i=1;i<m;i++){
            for(int j=0;j<=25;j++){
                if((sum1[r1[i+1]-1][j]-sum1[l1[i]][j])>0&&(sum2[r2[i+1]-1][j]-sum2[l2[i]][j])>0){
                    flag=true;
                    break;
                }
            }
        }
        for(int i=0;i<=25;i++){
            if(sum1[r1[1]-1][i]>0&&sum2[r2[1]-1][i]>0){
                flag=true;
                break;
            }
        }
        for(int i=0;i<=25;i++){
            if((sum1[n][i]-sum1[l1[m]][i]>0)&&(sum2[t][i]-sum2[l2[m]][i]>0)){
                flag=true;
                break;
            }
        }
        puts(flag?"1":"0");
    }
    return 0;
}