WA on #6
查看原帖
WA on #6
649114
50lty12楼主2023/7/13 19:19

RT

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,L1,L2,l,lz,cnt;
int nxt[N<<1];
char s[N<<1],t[N<<1],a[N<<1];
int zhuan(int l){
	int ss=0;
	for(int i=0; i<=l; i++) nxt[i]=0;
	for(int i=0; i<=l; i++) a[i]=' ';
	for(int i=1; i<=l/2; i++) a[++ss]=t[i];
	for(int i=L1-l/2+1; i<=L1; i++) a[++ss]=s[i];
//	printf("ss=%d\n",ss);
//	printf("%s\n",a+1);
	int j=0;
	nxt[1]=0;
	for(int i=2; i<=l; i++){
		while(j && a[j+1]!=a[i]) j=nxt[j];
		if(a[j+1]==a[i]) j++;
		nxt[i]=j;
	}
	return nxt[l];
}
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	L1=strlen(s+1);
	for(int i=2; i<=n; i++){
		scanf("%s",t+1);
		L2=strlen(t+1);
		l=min(L1,L2);
		lz=zhuan(l*2);
		for(int i=lz+1; i<=L2; i++) s[++L1]=t[i];
//		printf("lz=%d\n",lz);
		
	}
	printf("%s\n",s+1);
	return 0;
}
2023/7/13 19:19
加载中...