WA#3求教
查看原帖
WA#3求教
1032487
fhy2023楼主2024/7/7 21:30
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO
{
	#define p putchar
	#define g getchar
	inline int read()
	{
		int s=0,f=1;
		char ch=g();
		while(!('0'<=ch&&ch<='9'))
		{
			if(ch=='-')
			{
				f=-1;
			}
			ch=g();
		}
		while('0'<=ch&&ch<='9')
		{
			s=s*10+ch-'0';
			ch=g();
		}
		return s*f;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			p('-');
			x=-x;
		}
		if(x<10)
		{
			p(x+'0');
		}
		else
		{
			write(x/10);
			p(x%10+'0');
		}
	}
	#undef p
	#undef g
}
using IO::read;
using IO::write;
string s[100010];
int border[1000100];
string ans="";
inline void prepare(int x)
{
	int size=s[x].size();
	border[0]=0;
	for(int i=1,j=0;i<size;i++)
	{
		if(j&&s[x][j]!=s[x][i])
		{
			j=border[j-1];
		}
		if(s[x][j]==s[x][i])
		{
			j++;
		}
		border[i]=j;
	}
}
inline void find(int x)
{
	int ans_=0;
	prepare(x);
	int size=ans.size();
	for(int i=size-s[x].size()-1,j=0;i<size;i++)
	{
		while(j&&ans[i]!=s[x][j])
		{
			j=border[j-1];
		}
		if(ans[i]==s[x][j])
		{
			j++;
		}
		ans_=max(ans_,j);
	}
	for(int i=ans_;i<s[x].size();i++)
	{
		ans+=s[x][i];
	}
	return;
}
signed main()
{
	int n=read();
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
	}
	ans=s[1];
	for(int i=2;i<=n;i++)
	{
		find(i);
	}
	cout<<ans<<endl;
	return 0;
}
2024/7/7 21:30
加载中...