AC自动机

AC自动机就是用来处理在一个字符串中找多个模式串的问题。

假设有N个模式串，平均长度为L；文章长度为M。建立Trie树：O(N*L) 建立fail指针：O(N*L) 模式匹配：O(M*L) 所以，总时间复杂度为:O( (N+M)*L )。

典型例题见洛谷上这道模板题 https://www.luogu.org/problemnew/show/P3808

AC自动机相当于在Trie树上进行KMP，因为KMP每次只能对一个模式串进行匹配，而使用Trie树可以把多个模式串存入树中。

其中一大关键就是fail指针，相当于KMP中的next数组。他表示的就是当文本串和模式串失配的时候要跳转的节点。

以这张图为例，文本串是ushers，模式串是he， she， his， hers

当一个节点失配时，他的fail指针应指向他的父节点的fail指针指向节点的对应的子节点。

当一个节点没有对应的子节点时，应该让他的子节点指向他的fail指针指向的节点的对应子节点。

用BFS求出整棵树的fail指针。

query时就是不断沿着fail指针进行匹配。【类比KMP】

附上洛谷P3808AC代码

https://www.luogu.org/problemnew/show/P3808

 1 #include <iostream>
 2 #include <set>
 3 #include <cmath>
 4 #include <stdio.h>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 using namespace std;
11 typedef long long LL;
12 #define inf 0x7f7f7f7f
13 
14 int n;
15 const int maxn = 1e6 + 5;
16 
17 struct Tree{
18     int fail;//失配指针
19     int vis[26];//子节点位置
20     int ed;//标记有几个单词以这个节点结尾
21 }AC[maxn];
22 int cnt = 0;
23 
24 void build(string s)
25 {
26     int len = s.length();
27     int now = 0;//字典树当前指针
28     for(int i = 0; i < len; i++){
29         if(AC[now].vis[s[i] - 'a'] == 0){
30             AC[now].vis[s[i] - 'a'] = ++cnt;
31         }
32         now = AC[now].vis[s[i] - 'a'];
33     }
34     AC[now].ed += 1;
35 }
36 
37 void get_fail()
38 {
39     queue<int> que;
40     for(int i = 0; i < 26; i++){
41         if(AC[0].vis[i] != 0){
42             AC[AC[0].vis[i]].fail = 0;
43             que.push(AC[0].vis[i]);
44         }
45     }
46     while(!que.empty()){
47         int u = que.front();
48         que.pop();
49         for(int i = 0; i < 26; i++){
50             if(AC[u].vis[i] != 0){
51                 AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
52                 que.push(AC[u].vis[i]);
53             }
54             else{
55                 AC[u].vis[i] = AC[AC[u].fail].vis[i];
56             }
57         }
58     }
59 }
60 
61 int AC_query(string s)
62 {
63     int len = s.length();
64     int now = 0, ans = 0;
65     for(int i = 0; i < len; i++){
66         now = AC[now].vis[s[i] - 'a'];
67         for(int t = now; t && AC[t].ed != -1; t = AC[t].fail){
68             ans += AC[t].ed;
69             AC[t].ed = -1;
70         }
71     }
72     return ans;
73 }
74 
75 int main()
76 {
77     scanf("%d", &n);
78     string s;
79     for(int i = 0; i < n; i++){
80         cin>>s;
81         build(s);
82     }
83     AC[0].fail = 0;
84     get_fail();
85     cin>>s;
86     cout<<AC_query(s)<<endl;
87     return 0;
88 }

在附上洛谷P3796的模板题代码，这题统计多个模式串的出现次数。只需要把end改一下就好了。

https://www.luogu.org/problemnew/show/P3796

  1 #include <iostream>
  2 #include <set>
  3 #include <cmath>
  4 #include <stdio.h>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <queue>
  9 #include <map>
 10 using namespace std;
 11 typedef long long LL;
 12 #define inf 0x7f7f7f7f
 13 
 14 int n;
 15 const int maxn = 155 * 80;
 16 
 17 struct Tree{
 18     int fail;//失配指针
 19     int vis[26];//子节点位置
 20     int ed = -1;//标记有几个单词以这个节点结尾
 21 }AC[maxn];
 22 string s[155];
 23 int cnt[155];
 24 int tot = 0;
 25 
 26 void build(string s, int id)
 27 {
 28     int len = s.length();
 29     int now = 0;//字典树当前指针
 30     for(int i = 0; i < len; i++){
 31         if(AC[now].vis[s[i] - 'a'] == 0){
 32             AC[now].vis[s[i] - 'a'] = ++tot;
 33         }
 34         now = AC[now].vis[s[i] - 'a'];
 35     }
 36     AC[now].ed = id;
 37 }
 38 
 39 void get_fail()
 40 {
 41     queue<int> que;
 42     for(int i = 0; i < 26; i++){
 43         if(AC[0].vis[i] != 0){
 44             AC[AC[0].vis[i]].fail = 0;
 45             que.push(AC[0].vis[i]);
 46         }
 47     }
 48     while(!que.empty()){
 49         int u = que.front();
 50         que.pop();
 51         for(int i = 0; i < 26; i++){
 52             if(AC[u].vis[i] != 0){
 53                 AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
 54                 que.push(AC[u].vis[i]);
 55             }
 56             else{
 57                 AC[u].vis[i] = AC[AC[u].fail].vis[i];
 58             }
 59         }
 60     }
 61 }
 62 
 63 void AC_query(string s)
 64 {
 65     int len = s.length();
 66     int now = 0, ans = 0;
 67     for(int i = 0; i < len; i++){
 68         now = AC[now].vis[s[i] - 'a'];
 69         for(int t = now; t; t = AC[t].fail){
 70             if(AC[t].ed != -1){
 71                 cnt[AC[t].ed]++;
 72             }
 73 
 74             //ans += AC[t].ed;
 75             //AC[t].ed = -1;
 76         }
 77     }
 78     //return ans;
 79 }
 80 
 81 int main()
 82 {
 83     while(scanf("%d", &n) != EOF && n){
 84         memset(cnt, 0, sizeof(cnt));
 85         tot = 0;
 86         for(int i = 0; i < maxn; i++){
 87             AC[i].fail = 0;
 88             AC[i].ed = -1;
 89             for(int j = 0; j < 26; j++){
 90                 AC[i].vis[j] = 0;
 91             }
 92         }
 93         for(int i = 0; i < n; i++){
 94             cin>>s[i];
 95             build(s[i], i);
 96         }
 97         AC[0].fail = 0;
 98         get_fail();
 99         string str;
100         cin>>str;
101         AC_query(str);
102         int maxs = -1, maxid = 0;
103         for(int i = 0; i < n; i++){
104             if(maxs < cnt[i]){
105                 maxs = cnt[i];
106             }
107         }
108         cout<<maxs<<endl;
109         for(int i = 0; i < n; i++){
110             if(cnt[i] == maxs){
111                 cout<<s[i]<<endl;
112             }
113         }
114     }
115 
116     //cout<<s[maxid]<<endl;
117     //cout<<AC_query(s)<<endl;
118     return 0;
119 }