洛谷P3796 - 【模板】AC自动机（加强版）

原题链接

Description

模板题啦~

Code

//【模板】AC自动机（加强版）
#include <cstdio>
#include <cstring>
int const N=2e5;
int const L=1e6+10;
int n;
char s1[200][80],s2[L];
int rt,ndCnt;
int ch[N][26],val[N],fail[N],pre[N];
void ins(char s[],int id)
{int len=strlen(s),p=rt;for(int x=0;x<len;x++){int i=s[x]-'a';if(!ch[p][i]) ch[p][i]=++ndCnt;p=ch[p][i];}val[p]=id;
}
int Q[L],op,cl;
void buildAC()
{Q[++cl]=rt;while(op<cl){int p=Q[++op];for(int i=0;i<26;i++){int q=ch[p][i],p1=fail[p];if(!q) {ch[p][i]=ch[p1][i]; continue;}fail[q]=ch[p1][i];pre[q]=val[fail[q]]?fail[q]:pre[fail[q]];Q[++cl]=q;}}
}
int cnt[200];
void query(char s[])
{memset(cnt,0,sizeof cnt);int len=strlen(s),p=rt;for(int x=0;x<len;x++){p=ch[p][s[x]-'a'];for(int t=p;t;t=pre[t]) cnt[val[t]]++;}
}
int main()
{while(true){scanf("%d",&n); if(!n) break;ndCnt=0,rt=++ndCnt;memset(ch,0,sizeof ch); memset(val,0,sizeof val);memset(fail,0,sizeof fail); memset(pre,0,sizeof pre);for(int i=0;i<26;i++) ch[0][i]=rt;for(int i=1;i<=n;i++) scanf("%s",s1[i]),ins(s1[i],i);buildAC();scanf("%s",s2); query(s2);int ans=0;for(int i=1;i<=n;i++) if(cnt[i]>ans) ans=cnt[i];printf("%d\n",ans);for(int i=1;i<=n;i++) if(cnt[i]==ans) puts(s1[i]);}return 0;
}