萌新WA on #4求助
查看原帖
萌新WA on #4求助
390034
heumo7at楼主2021/10/24 22:08
using fastIO::read;
using fastIO::gc;
char str[100400][1000];
int pi[1001];
int ans[100400];
int main(){
	//freopen("temp.in","r",stdin);
	//freopen("temp.out","w",stdout);
	mt19937_64 ran(time(0));
	int n;cin >> n;
	gc();
	for(int i=n;i;i--){
		char x = gc();int tot=0;
		while(x!='\n' && x!='\r' && x!=' '){
			str[i][tot++]=x;x=gc();
		}
	}
	memset(ans,0x3f,sizeof ans);
	for(int i=1;i<n;i++){
		memset(pi,0,sizeof pi);
		const int len = min(strlen(str[i]),strlen(str[i+1]));
		char x[1000];
		int k=0;
		const int sz2 = strlen(str[i+1]);
		for(int z=0;z<len;z++)x[k++]=str[i][z];
		for(int t=1;t<=10;t++)x[k++]=(ran()%88)+10;
		for(int z=sz2-len;z<sz2;z++)x[k++]=str[i+1][z];
		for(int t=1;t<k;t++){
			int j=pi[t-1];
			while(j && x[j]!=x[t]){
				j=pi[j-1];
			}
			if(x[j]==x[t])j++;
			pi[t]=j;
		}
		ans[i+1]=(int)strlen(str[i+1])-pi[k-1];
	}
	for(int i=n;i;i--){
		const int len = strlen(str[i]);
		for(int j=0;j<min(len,ans[i]);j++)cout << str[i][j];
	}putchar('\n');
    return 0;
}
2021/10/24 22:08
加载中...