AC自动机(Aho-Corasick automation)模板

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 using namespace std;
 6 const int maxn = 1000010;
 7 char S[1000010];
 8 struct AC{
 9     int ch[maxn][27],fail[maxn],end[maxn],root,cnt;
10     void Init()
11     {    memset(ch,0,sizeof(ch));memset(fail,0,sizeof(fail));
12         memset(end,0,sizeof(end));cnt=0;root=0;
13     }
14     void Insert(char *s)
15     {    int len=strlen(s),node=root;
16         for(int i=0;i<len;i++)
17         {    if(ch[node][s[i]-‘`‘])
18                 node=ch[node][s[i]-‘`‘];
19             else
20                 node=ch[node][s[i]-‘`‘]=++cnt;    
21         }
22         end[node]++;
23     }
24     void Build()
25     {
26         queue<int>q; 
27         for(int i=1;i<=26;i++)
28             if(ch[root][i]) 
29                 fail[ch[root][i]]=root,q.push(ch[root][i]);
30             else 
31                 ch[root][i]=root;
32         while(!q.empty())
33         {    int node=q.front();q.pop();
34             for(int i=1;i<=26;i++)
35             {    if(ch[node][i]){
36                     fail[ch[node][i]]=ch[fail[node]][i];
37                     q.push(ch[node][i]);
38                 }
39                 else
40                     ch[node][i]=ch[fail[node]][i];
41             }
42         }
43     }
44     int Query(char *s)
45     {    int len=strlen(s),node=root,ret=0;
46         for(int i=0;i<len;i++)
47         {    node=ch[node][s[i]-‘`‘];
48             int temp=node;
49             while(temp!=root)
50                 ret+=end[temp],end[temp]=0,temp=fail[temp];    
51         }
52         return ret;
53     }
54 }A;
55 int main()
56 {
57     int Q;
58     scanf("%d",&Q);
59     int n;
60     while(Q--)
61     {    scanf("%d",&n);
62         A.Init();
63         for(int i=1;i<=n;i++)
64         {    scanf("%s",S);
65             A.Insert(S);
66         }
67         A.Build();
68         scanf("%s",S);
69         printf("%d\n",A.Query(S));
70     }
71     return 0;
72 }