玄学现象
查看原帖
玄学现象
601747
xibaohe楼主2023/10/12 21:48

以下是第一篇题解中经过组合的AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int nxt[1000005];//next数组(不要写next,在CF上是关键字,会CE)
void kmp(string s){//我懒得讲KMP了怎么办啊QwQ
	int l=s.size();
	s=' '+s;//前面加个空格,让s下标从1开始
	nxt[0]=nxt[1]=0;//初始化next数组
	int j=0;//下标
	for(int i=2;i<=l;i++){
		while(j>0&&s[i]!=s[j+1])j=nxt[j];//如果不匹配,就借用已知信息跳到next
		if(s[i]==s[j+1])j++;//匹配成功!j++;
		nxt[i]=j;//更新next数组的信息
	} 
}
int main(){
    ios::sync_with_stdio(false);//让cin变得快一点
	int n;
    cin>>n;
	string s,ans;
	cin>>ans;//先拿第一个字符串当成答案,后面逐步合并
	for(int i=2;i<=n;i++){
		cin>>s;//输入
		int l=min(s.size(),ans.size());
		string ss=s+"IFUCKCCF!"+ans.substr(ans.size()-l,l);//构造新的字符串
		kmp(ss);//进行kmp
		for(int j=nxt[ss.size()];j<s.size();j++)//更新不是公共部分(也就是下标>=next[ss.size()]的部分)到ans里
		ans+=s[j];
	}
	cout<<ans;//输出
} 

容易发现,KMP函数中的nxt数组(也称fail数组)只需要开到1000005即可AC。

我的代码与第一篇题解思路类似,但是nxt数组开到1000005就会WA(错误信息显示为nxt数组下标越界)。

record

当MAXN开到10000005就能AC了。

record-AC

2023/10/12 21:48
加载中...