AC自动机模板

 1 ///AC自动机模板
 2 void insert(char *s)
 3 {
 4     int p=0;
 5     for (int i=0;s[i];i++)
 6     {
 7         int k=s[i]-'a';
 8         if (tree[p].next[k]==-1)
 9         {
10             tree[cut].init(k);
11             tree[p].next[k]=cut++;
12         }
13         p=tree[p].next[k];
14     }
15     tree[p].count++;
16 }
17 
18 void ac()
19 {
20     int k=0;
21     queue<Node>q;
22     q.push(tree[0]);
23     while (!q.empty())
24     {
25         Node u=q.front();
26         q.pop();
27         for (int i=0;i<26;i++)
28         {
29             if (u.next[i]!=-1)
30             {
31                 if (u.data==-1) tree[u.next[i]].fail=0;
32                 else
33                 {
34                     int v=u.fail;
35                     while (v&&tree[v].next[i]==-1) v=tree[v].fail;
36                     tree[u.next[i]].fail=max(tree[v].next[i],0);
37                 }
38                 q.push(tree[u.next[i]]);
39             }
40         }
41     }
42 }
43 
44 int getans(char *s)
45 {
46     int k=0,ans=0;
47     for (int i=0;s[i];i++)
48     {
49         int x=s[i]-'a';
50         while (k&&tree[k].next[x]==-1) k=tree[k].fail;
51         k=tree[k].next[x];
52         if (k==-1) {k=0;continue;}
53         int j=k;
54         while (tree[j].count)
55         {
56             ans+=tree[j].count;
57             tree[j].count=0;
58             j=tree[j].fail;
59         }
60         ans+=tree[tree[j].fail].count;
61         tree[tree[j].fail].count=0;
62     }
63     return ans;
64 }