感觉字符串只会 hash 了。
这里提几点易错点：
① 字符串能不用 string 就不用。 反正这道题因为 string 的 size （不能正常清空）和读入 Wa 飞了
② hash 都写双模数。单模数太容易被卡。
#include<bits/stdc++.h>
using namespace std;
const int mod[2]={998244353,1000000007},Len=1000007,P[2]={131,127};
int head[Len],nex[10000001],ans[10000001],st[10000001],ed[10000001],tot;
int h[2][1000005],p[2][1000005],hh[2][12];
char ss[1000007],s[12];
inline int get(int typ,int l,int r){
if(l>r)return 0;
return ((h[typ][r]-1ll*h[typ][l-1]*p[typ][r-l+1]%mod[typ])%mod[typ]+mod[typ])%mod[typ];
}
inline int gethh(int typ,int l,int r){
if(l>r)return 0;
return ((hh[typ][r]-1ll*hh[typ][l-1]*p[typ][r-l+1]%mod[typ])%mod[typ]+mod[typ])%mod[typ];
}
inline bool pd(int l1,int r1,int l2,int r2){
if(r1-l1!=r2-l2)return 0;
for(int i=0;i<=r1-l1;++i){
if(ss[l1+i]!=ss[l2+i])return 0;
}
return 1;
}
inline bool pd2(int l1,int r1,int l2,int r2){
if(r1-l1!=r2-l2)return 0;
for(int i=0;i<=r1-l1;++i){
if(ss[l1+i]!=s[l2+i])return 0;
}
return 1;
}
int main(){
// cout<<(sizeof(ss)>>20)<<endl;
//std::ios::sync_with_stdio(false);
scanf("%s",1+ss);
int n=strlen(1+ss);
// cout<<n<<endl;
// ss='0'+ss;
for(int t=0;t<2;++t){
p[t][0]=1;
for(int i=1;i<=n;++i)h[t][i]=(1ll*h[t][i-1]*P[t]%mod[t]+ss[i]-'a'+1)%mod[t],p[t][i]=1ll*p[t][i-1]*P[t]%mod[t];
for(int i=1;i<=10;++i)p[t][i]=1ll*p[t][i-1]*P[t]%mod[t];
}
for(int len=0;len<n;++len){
if(get(0,1,len)==get(0,n-len+1,n)&&get(1,1,len)==get(1,n-len+1,n)){
for(int i=1;i<=min(n-len,10);++i){
int sum=get(0,len+1,len+i)%Len,j=head[sum];
while(j){
if(pd(st[j],ed[j],len+1,len+i)){
ans[j]=len;
break;
}
}
if(!j){
nex[++tot]=head[sum],head[sum]=tot;ans[tot]=len;st[tot]=len+1,ed[tot]=len+i;
}
}
}
}
// cout<<get(1,1)<<" "<<get(n,n)<<endl;
// for(int i=1;i<=tot;++i)cout<<ss[i]<<endl;
int q;scanf("%d",&q);
while(q--){
scanf("%s",1+s);
int t=strlen(1+s);
// cout<<t<<endl;
for(int i=1;i<=t;++i){
for(int T=0;T<2;++T)hh[T][i]=(1ll*hh[T][i-1]*P[T]+s[i]-'a'+1)%mod[T];
int Ans=0;
int j=head[hh[0][i]%Len];
while(j){
if(pd2(st[j],ed[j],1,i)){
Ans=max(Ans,ans[j]+i);
break;
}
j=nex[j];
}
for(int len=max(1,n-i+1);len<n;++len){
if((1ll*get(0,n-len+1,n)*p[0][i]+hh[0][i])%mod[0]==(1ll*get(0,1,n)*p[0][i-n+len]%mod[0]+hh[0][i-n+len])%mod[0]&&
(1ll*get(1,n-len+1,n)*p[1][i]+hh[1][i])%mod[1]==(1ll*get(1,1,n)*p[1][i-n+len]%mod[1]+hh[1][i-n+len])%mod[1])Ans=max(Ans,len+i);
}
for(int len=1;len<=min(i,n);++len){
if(gethh(0,i-len+1,i)==get(0,1,len)&&gethh(1,i-len+1,i)==get(1,1,len))Ans=max(Ans,len);
}
if(i>n){
for(int len=n+1;len<=i;++len){
if(gethh(0,i-len+1,i)==(1ll*get(0,1,n)*p[0][len-n]%mod[0]+gethh(0,1,len-n))%mod[0]&&
gethh(1,i-len+1,i)==(1ll*get(1,1,n)*p[1][len-n]%mod[1]+gethh(1,1,len-n))%mod[1])Ans=max(Ans,len);
}
}
printf("%d ",Ans);
}
puts("");
}
return 0;
}
/*
string size cin
hash
detail
*/
下面给出字符串做法。
其实看到 prefix function 就应该想到 kmp 的了。
最自然朴素的做法就是预处理 \(s\) 的 \(nex\) 数组，然后每次从 \(|s|+1\) 开始跑 \(s+t\)。
虽然单纯的 kmp 时间复杂度是 \(O(N)\)，但若是 \(s=aaa...aaa,t=b\) 那每次都得跑 \(O(N)\)，这样肯定会 TLE。
注意到复杂度瓶颈在于 \(nex\) 的跳动。那么我们设 \(kmp[i][k]\) 表示 \(i\) 所对应的 \(j,nex[j],nex[nex[j]]...\) 中，下一位为 \('a'+k\) 的最右位置，每次直接跳到对应位置。
这样总复杂度就稳定在 \(O(N\times |C|)\)
#include<bits/stdc++.h>
using namespace std;
#define N 1000015
int kmp[N][26];
char s[N],t[12];
inline int init(int n){
for(int i=1,j=0;i<=n;++i){
if(i!=1){
if(!(j+1!=i&&s[j+1]==s[i]))j=kmp[j][s[i]-'a'];
if(s[j+1]==s[i])++j;
}
for(int k=0;k<26;++k)kmp[i][k]=kmp[j][k];
kmp[i][s[j+1]-'a']=j;
if(i==n)return j;
}
}
int main(){
scanf("%s",1+s);
int q,n,m;cin>>q;
n=strlen(1+s);
int las=init(n);
while(q--){
scanf("%s",1+t);
m=strlen(1+t);
for(int i=n+1,j=las;i<=m+n;++i){
s[i]=t[i-n];
if(!(j+1!=i&&s[j+1]==s[i]))j=kmp[j][s[i]-'a'];
if(s[j+1]==s[i])++j;
printf("%d ",j);
for(int k=0;k<26;++k)kmp[i][k]=kmp[j][k];
kmp[i][s[j+1]-'a']=j;
}
puts("");
}
return 0;
}