AC自动机模板
描述 有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串T中出现的次数最多。
输入 输入含多组数据。
每组数据的第一行为一个正整数N，表示共有N个模式串，1≤N≤150。
接下去NN行，每行一个长度小于等于70的模式串。下一行是一个长度小于等于10^6 的文本串T。
输入结束标志为N=0
输出 对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。
样例输入 [复制] 2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0 样例输出 [复制] 4 aba 2 alpha haha
#include<bits/stdc++.h> using namespace std; inline int read() { int data=0;int w=1; char ch=0; ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar(); return data*w; } const int N=6e5+10; int n; char mob[200][200]; int ch[N][27],fail[N],ans[N]; char s[10000001]; int num[N],siz=0; inline void insert(char s[],int v){ int now=0,len=strlen(s); for(int i=0;i<len;i++){ int o=s[i]-'a'; if(!ch[now][o]) ch[now][o]=++siz; now=ch[now][o]; } num[now]=v; } inline void getfail(){ queue<int>que; for(int i=0;i<26;i++)if(ch[0][i])que.push(ch[0][i]),fail[ch[0][i]]=0; while(!que.empty()){ int u=que.front();que.pop(); for(int i=0;i<26;i++){ int v=ch[u][i]; if(v)fail[v]=ch[fail[u]][i],que.push(v); else ch[u][i]=ch[fail[u]][i]; } } } inline void query(char s[]){ int now=0,len=strlen(s); for( int i=0;i<len;i++){ now=ch[now][s[i]-'a']; for(int j=now;j;j=fail[j])ans[num[j]]++; } } int main(){ while(1){ n=read(); if(n==0) break; memset(num,0,sizeof(num)); memset(ans,0,sizeof(ans)); memset(ch,0,sizeof(ch)); memset(fail,0,sizeof(fail)); siz=0; for(int i=1;i<=n;i++){scanf("%s",mob[i]),insert(mob[i],i);} getfail();scanf("%s",s);query(s);int temp=0; for(int i=1;i<=n;i++)temp=max(ans[i],temp); printf("%d\n",temp); for(int i=1;i<=n;i++) if(ans[i]==temp) printf("%s\n",mob[i]); } }