以下是第一篇题解中经过组合的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数组下标越界)。
当MAXN开到10000005就能AC了。