自动搬运

查看原文

来自洛谷，原作者为

	jinminghao 1e18

搬运于2025-08-24 23:17:38，当前版本为作者最后更新于2025-07-08 13:35:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

举个例子：

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;
}