萌新求助KMP,第57个点WA
查看原帖
萌新求助KMP,第57个点WA
431487
_zdc_楼主2021/7/8 16:12

RT

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,x,len1,len2,nxt[N],f[N];
char s[N],s2[N];
void merge(){
	x=nxt[1]=0;
	for(int i=2;i<=len2;i++){
		while(x && s[i]!=s[x+1]) x=nxt[x];
		if(s2[i]==s2[x+1]) x++;
		nxt[i]=x;
	}
	x=0;
	for(int i=max(1,len1-len2+1);i<=len1;i++){
		while(x && (x==len1 || s[i]!=s2[x+1])) x=nxt[x];
		if(s[i]==s2[x+1]) x++;
		f[i]=x;
	}
	x=len1-f[len1]+1;
	for(int i=1;i<=len2;i++){
		s[x]=s2[i];
		x++;
	}
	len1=len1+len2-f[len1];
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>(s+1);
	len1=strlen(s+1);
	n--;
	while(n--){
		cin>>(s2+1);
		len2=strlen(s2+1);
		merge();
	}
	for(int i=1;i<=len1;i++) cout<<s[i];
	return 0;
}
2021/7/8 16:12
加载中...