暴跳 fail 都能过的吗（
by xgzc @ 2019-11-09 08:00:12
看来要有一个加强的加强版(
by Ameiyo @ 2019-11-09 08:01:28
@[此店不售此书](/user/103434) 那是因为您暴力跳的 fail
by Karry5307 @ 2019-11-09 08:03:28
@[Karry5307](/user/60990) 是这样的吗？我一直以为我在用正解写的qwq
by 此店不售此书 @ 2019-11-09 08:06:17
```c
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define res register int
const int MAXN=1000000+10;
char S[160][80],T[MAXN];
int n,maxn;
queue<int> q;
struct AC{
int cnt,c[MAXN][26],fail[MAXN],g[MAXN],isend[MAXN],ans[MAXN];
inline void Ins(char *A,int ID){
int len=strlen(A),x=0;
for(res i=0;i<len;++i){
if(!c[x][A[i]-'a']) c[x][A[i]-'a']=++cnt;
x=c[x][A[i]-'a'];
}
isend[x]=ID;
}
inline void get_fail(){
for(res i=0;i<26;++i){
if(c[0][i]) fail[c[0][i]]=0,q.push(c[0][i]);
}
while(!q.empty()){
int x=q.front(); q.pop();
for(res i=0;i<26;++i){
if(!c[x][i]){
c[x][i]=c[fail[x]][i];
continue;
}
fail[c[x][i]]=c[fail[x]][i];
g[c[x][i]]=isend[fail[c[x][i]]]?fail[c[x][i]]:g[fail[c[x][i]]];
q.push(c[x][i]);
}
}
}
inline void query(char *A){
int len=strlen(A),x=0;
for(res i=0;i<len;++i){
x=c[x][A[i]-'a'];
for(res t=x;t;t=g[t]) ++ans[isend[t]];
}
}
inline void init(){
maxn=0,cnt=0;
memset(c,0,sizeof(c));
memset(g,0,sizeof(g));
memset(ans,0,sizeof(ans));
memset(fail,0,sizeof(fail));
memset(isend,0,sizeof(isend));
}
}Ac;
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
while(scanf("%d",&n)&&n){
Ac.init();
for(res i=1;i<=n;++i){
scanf("%s",S[i]);
Ac.Ins(S[i],i);
}
Ac.get_fail();
scanf("%s",T);
Ac.query(T);
for(res i=1;i<=n;++i) if(Ac.ans[i]>maxn) maxn=Ac.ans[i];
printf("%d\n",maxn);
for(res i=1;i<=n;++i) if(Ac.ans[i]==maxn) printf("%s\n",S[i]);
}
return 0;
}
```
我裂开了，看题解加了个g数组，还是9s左右，我还是写错了吗？@[Karry5307](/user/60990)
by 此店不售此书 @ 2019-11-09 08:27:15
@[此店不售此书](/user/103434) 因为泥可爱鸭qwq
by 溪水瑶 @ 2019-11-09 08:41:19
@[溪水瑶](/user/211229) qwq
by 此店不售此书 @ 2019-11-09 08:42:32
@[此店不售此书](/user/103434) qmq
by 溪水瑶 @ 2019-11-09 08:43:19
暴跳fail又长又丑，建议换成trie图
by Smile_Cindy @ 2020-01-27 17:10:54