至于AC自动机基础的话推荐yyb's blog
如果看了还是不会的话就像我一样啃一整天画个图想一想就好啦
AC自动机其实就是一种多模匹配算法，他约等于KMP思想+Trie结构（反正说了也没用）
这道题主要是注意统计答案，可以在标记end时记上顺序并在统计答案时用结构体记录
然后数据有很多组注意清零（我因为ans没清零WA了n次）
Code:（与yyb的代码有相似之处毕竟是看着学的嘛）
1 #include<bits/stdc++.h> 2 #define debug cout<<"AJH AK IOI!!!"<<endl 3 using namespace std; 4 int cnt,n; 5 string ss[160]; 6 struct Node { 7 int fail,ed,son[26]; 8 }tr[100510]; 9 struct Ans {//统计答案，ct为出现次数，idx为编号（输出用） 10 int ct,idx; 11 }ans[100510]; 12 inline bool cmp(Ans a,Ans b){ 13 if(a.ct==b.ct)return a.idx<b.idx; 14 return a.ct>b.ct; 15 } 16 inline void Clear(int now){ 17 tr[now].ed=0; 18 tr[now].fail=0; 19 memset(tr[now].son,0,sizeof(tr[now].son)); 20 } 21 inline void Insert(string s,int nownum){ 22 int len=s.length(),now=0,tmp; 23 for(int i=0;i<len;i++){ 24 tmp=s[i]-'a'; 25 if(!tr[now].son[tmp]){ 26 tr[now].son[tmp]=++cnt;//AC自动机基础操作，注意清零 27 Clear(cnt); 28 } 29 now=tr[now].son[tmp]; 30 } 31 tr[now].ed=nownum;//插入单词时记录顺序 32 } 33 inline void Fail(){ 34 queue<int>q; 35 for(int i=0;i<26;i++){ 36 if(tr[0].son[i]){ 37 tr[tr[0].son[i]].fail=0; 38 q.push(tr[0].son[i]); 39 } 40 } 41 while(!q.empty()){ 42 int now=q.front(); 43 q.pop(); 44 for(int i=0;i<26;i++){ 45 if(tr[now].son[i]){ 46 tr[tr[now].son[i]].fail=tr[tr[now].fail].son[i]; 47 //非常巧妙的操作，避免了一步一步向上跳 48 //可以想一想为什么（其实我也没搞懂但是这行代码太好背了） 49 q.push(tr[now].son[i]); 50 } else{ 51 tr[now].son[i]=tr[tr[now].fail].son[i]; 52 } 53 } 54 } 55 } 56 inline void Find(string s){ 57 int len=s.length(),now=0,tmp; 58 for(int i=0;i<len;i++){ 59 tmp=s[i]-'a'; 60 now=tr[now].son[tmp]; 61 for(int j=now;j;j=tr[j].fail){ 62 ans[tr[j].ed].ct++;//找完一个单词记到ans里 63 } 64 } 65 } 66 int main(){ 67 while(114514){//这里可能有点臭 68 cin>>n; 69 if(n==0)break; 70 Clear(0); 71 cnt=0; 72 for(int i=1;i<=n;i++){ 73 cin>>ss[i]; 74 ans[i].ct=0;//这句话害我WA半天 75 ans[i].idx=i; 76 Insert(ss[i],i); 77 } 78 Fail(); 79 cin>>ss[0]; 80 Find(ss[0]); 81 sort(ans+1,ans+n+1,cmp); 82 //输出结果 83 cout<<ans[1].ct<<endl; 84 cout<<ss[ans[1].idx]<<endl; 85 for(int i=2;i<=n;i++){ 86 if(ans[i].ct==ans[i-1].ct){ 87 cout<<ss[ans[i].idx]<<endl; 88 }else break; 89 } 90 ////////// 91 } 92 return 0;//功德園满 93 }