MnZn刚学OI,#3TLE求助
查看原帖
MnZn刚学OI,#3TLE求助
767353
Oct0pus1楼主2023/1/24 17:51

rt

#include<bits/stdc++.h>
using namespace std;
const int L=1e5+10;
string str[L],cur;
int n,pi[L];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>str[i];
	cur=str[1];
	for(int i=2;i<=n;i++){
		string tmp;
		int szi=str[i].size(),szc=cur.size();
		if(szi==szc)tmp=str[i]+cur;
		else if(szi>szc)tmp=str[i].substr(0,szc)+cur;
		else tmp=str[i]+cur.substr(szc-szi,szi);
		int szt=tmp.size();
		memset(pi,0,sizeof(int)*(szt+5));
		for(int i=1;i<szt;i++){
			int j=pi[i-1];
			while(j>0 && tmp[i]!=tmp[j])j=pi[j-1];
			if(tmp[i]==tmp[j])j++;
			pi[i]=j;
		}
		if(pi[szt-1]>=szc)cur=szi>szc?str[i]:cur;
		else cur=cur.substr(0,szc-pi[szt-1])+str[i];
	}
	cout<<cur;
	return 0;
}
2023/1/24 17:51
加载中...