自动AC机qwq（大雾）以及trie图fail图的一些结论

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<queue>
 6 #include<algorithm>
 7 #include<cmath>
 8 using namespace std;
 9 const int MAX=1e6,TYPE=26;
10 struct ac_automation{
11     int trie[MAX][TYPE],num[MAX],tot,fail[MAX];
12     void readin(char * a)
13     {
14         int k=strlen(a),now=0;
15         for(int i=0;i<k;i++)
16         {
17             if(!trie[now][a[i]-'a'])
18                 trie[now][a[i]-'a']=++tot;
19             now=trie[now][a[i]-'a'];
20         }
21         num[now]++;
22     }
23     void getfail()
24     {
25         queue<int> q;
26         memset(fail,0,sizeof(fail));
27         for(int i=0;i<TYPE;i++)
28             if(trie[0][i])
29                 q.push(trie[0][i]);
30         while(!q.empty())
31         {
32             int k=q.front();
33             q.pop();
34             for(int i=0;i<TYPE;i++)
35                 if(trie[k][i])    
36                 {
37                     fail[trie[k][i]]=trie[fail[k]][i];
38                     q.push(trie[k][i]);
39                 }
40                 else
41                     trie[k][i]=trie[fail[k]][i];
42         }
43     }
44     int find(char *s)
45     {
46         int ans=0,p=0;
47         for(int i=0;s[i];i++)
48         {
49             p=trie[p][s[i]-'a'];
50             for(int j=p;j and ~num[j];j=fail[j])    ans+=num[j],num[j]=-1;
51         }
52         return ans;
53     }
54 }ac; 
55 char str[MAX],tem[MAX];
56 int main()
57 {
58     int k;
59     scanf("%d",&k);
60     for(int i=1;i<=k;i++)
61     {
62         scanf("%s",tem);
63         ac.readin(tem);
64     }
65     scanf("%s",str);
66     ac.getfail();
67     printf("%d",ac.find(str));
68     return 0;
69 }

二、一些结论

　　1.x的fail指针指向的是x点在这个trie中代表的字符串的在这个trie中的最长后缀

　　2.对于一个不在自动机中的字符串s，将其放到自动机中跑，最后停下来时，即到达s的最后一个字符时，假设此时在ac自动机中到了y节点，则y点代表的字符串就是s的最长的，是ac自动机中的字符串的前缀，的后缀。

　　3.第一次失配的位置深度（=最长前缀）,结束时所在节点深度（=最长后缀）;