WA on 3求调(KMP)
查看原帖
WA on 3求调(KMP)
1063615
Scez楼主2024/11/20 09:01
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=1e6+1e5;
int n;
string c[114514];
string ans;
int nxt[N]; 
void find_next(string s)
{
	int i=1,j=0;
	while(i<s.length())
	{
		if(s[i]==s[j])
		{
			nxt[i]=j+1;
			i++,j++;
		} 
		else
		{
			while(j&&s[i]!=s[j])
			j=nxt[j-1];
			if(!j)
			nxt[i]=0,i++;
			else
			nxt[i]=j+1,i++,j++;
		}
	}
}
int main()
{
//	freopen("","r",stdin);
//	freopen("","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>c[i];
	ans=c[1];
	for(int i=2;i<=n;i++)
	{ 
		int len=min(c[i].length(),ans.length());
		string c1=c[i]+"($@#&)"+ans.substr(ans.length()-len,len);
		find_next(c1);
		for(int j=nxt[c1.length()-1];j<c[i].length();j++)
		ans+=c[i][j];
	}
	cout<<ans;
	return 0;
}


cf评测上显示的答案和输出片段一样,看不出来哪里错了

2024/11/20 09:01
加载中...