P5357 【模板】AC自动机（二次加强版）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e6+10;
 4 struct AC{
 5     int son[26];
 6     int flag,fail;
 7 }trie[150*80];
 8 int n,cnt;
 9 char s[maxn];
10 queue<int>q;
11 string zifu[200];
12 int sto[maxn]; int num=0;
13 int mx=0;
14 int vis[maxn];
15 void init()
16 {
17     while(!q.empty()) q.pop();
18     memset(vis,0,sizeof(vis));
19     memset(trie,0,sizeof(trie));
20     memset(sto,0,sizeof(sto));
21     mx=0;cnt=0;
22     num=0;
23 }
24 void Insert(int x)
25 {
26     int u=1,len=zifu[x].size();
27     for(int i=0;i<len;i++){
28         int v=zifu[x][i]-‘a‘;
29         if(!trie[u].son[v])
30             trie[u].son[v]=++cnt;
31         u=trie[u].son[v];
32     }
33     vis[u]=++num;
34     trie[u].flag++;
35 }
36 void getFail()
37 {
38     for(int i=0;i<26;i++)
39         trie[0].son[i]=1;          //初始化0的所有儿子都是1
40     q.push(1);trie[1].fail=0;               //将根压入队列
41     while(!q.empty()){
42         int u=q.front();q.pop();
43         for(int i=0;i<26;i++){              //遍历所有儿子
44             int v=trie[u].son[i];           //处理u的i儿子的fail，这样就可以不用记父亲了
45             int Fail=trie[u].fail;          //就是fafail，trie[Fail].son[i]就是和v值相同的点
46             if(!v){
47                 trie[u].son[i]=trie[Fail].son[i];
48                 continue;
49             }  //不存在该节点，第二种情况
50             trie[v].fail=trie[Fail].son[i]; //第三种情况，直接指就可以了
51             q.push(v);                      //存在实节点才压入队列
52         }
53     }
54 }
55 int query(char* s)
56 {
57     int u=1,ans=0,len=strlen(s);
58     for(int i=0;i<len;i++){
59         int v=s[i]-‘a‘;
60         int k=trie[u].son[v];       //跳Fail
61         while(k>1){   //经过就不统计了
62             ans+=trie[k].flag;    //累加上这个位置的模式串个数
63             sto[vis[k]]+=trie[k].flag;
64             mx=max(mx,sto[vis[k]]);
65             k=trie[k].fail;         //继续跳Fail
66         }
67         u=trie[u].son[v];           //到下一个儿子
68     }
69     return ans;
70 }
71 int main(){
72     while(scanf("%d",&n)!=EOF){
73         init();
74         if(!n) break;
75         cnt=1;
76         for(int i=1;i<=n;i++){
77             cin>>zifu[i];
78             Insert(i);
79         }
80         getFail();
81         scanf("%s",s);
82         query(s);
83         printf("%d\n",mx);
84         for(int i=1;i<=n;i++){
85             if(mx==sto[i])
86                 cout<<zifu[i]<<endl;
87         }
88     }
89     return 0;
90 }