ABC329E
  • 板块学术版
  • 楼主AKPC
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/18 21:41
  • 上次更新2023/11/19 11:06:45
查看原帖
ABC329E
540363
AKPC楼主2023/11/18 21:41

F<E

E 是咋错的,AC x31 WA x20

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
string a,b;
char c[200005];
int A=read(),B=read(),nxt[200005];
bitset<200005>tmp;
signed main(){
	cin>>a>>b,a=' '+a,b=' '+b;;
	for (int i=2,j=0;i<=B;i++){
		while (j>0&&b[i]!=b[j+1]) j=nxt[j];
		if (b[i]==b[j+1]) j++;
		nxt[i]=j;
	}
	for (int i=1,j=0;i<=A;i++){
		while (j>0&&a[i]!=b[j+1]) j=nxt[j];
		if (a[i]==b[j+1]) j++;
		if (j==B) tmp[i-B+1]=1;
	}
	for (int i=1;i<=A;i++) c[i]='#';
	for (int i=1;i<=A;i++){
		if (!tmp[i]) continue;
		for (int j=2;j<=B;j++) tmp[i+j-1]=1;
		i+=B;
	}
	for (int i=1;i<=A;i++){
		if (tmp[i]) continue;
//		cout<<i<<'\n';
		for (int j=B;j>=1;j--){
			if (b[j]!=a[i]) continue;
//			cout<<j<<'\n';
			for (int k=1;k<=B-j+1;k++){
				int id=i+k-1;
				if (id>A) break;
				if (c[id]!='#'&&c[id]!=b[j+k-1]){
//					cout<<id<<' '<<c[id]<<' '<<b[j+k-1]<<'\n';
					puts("No");
					return 0;
				}
				c[id]=b[j+k-1];
			}
		}
//		for (int i=1;i<=A;i++) cout<<c[i];cout<<'\n';
	}
	puts("Yes");
	return 0;
}
2023/11/18 21:41
加载中...