首页 > 代码库 > AC自动机专题

AC自动机专题

2024-07-05 20:09:41   235人阅读

AC自动机简介：KMP是用于解决单模式串匹配问题， AC自动机用于解决多模式串匹配问题。

精华：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root。

如果用KMP来解决多模式串匹配问题，则复杂度为O(n + k * m), 而AC自动机的负责度为O(n + m + z), z为模式串出现的次数。

学习链接：

http://hi.baidu.com/nialv7/item/ce1ce015d44a6ba7feded52d

http://blog.csdn.net/niushuai666/article/details/7002823

http://www.cnblogs.com/kuangbin/p/3164106.html

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2222

思路：AC自动机的入门题，用的是bin牛的模板，统计End数组即可，统计过的需要清0.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
 7 #define REP(i, a, b) for (int i = (a); i <= (b); ++i)
 8 using namespace std;
 9 
10 const int MAX_N = (500000 + 500);
11 struct Trie {
12     int next[MAX_N][26], End[MAX_N], fail[MAX_N];
13     int root, L;
14     int NewNode()
15     {
16         FOR(i, 0, 26) next[L][i] = -1;
17         End[L++] = 0;
18         return L - 1;
19     }
20     void Init()
21     {
22         L = 0;
23         root = NewNode();
24     }
25     void Insert(char *str)
26     {
27         int len = strlen(str), now = root;
28         FOR(i, 0, len) {
29             int id = str[i] - ‘a‘;
30             if (next[now][id] == -1) next[now][id] = NewNode();
31             now = next[now][id];
32         }
33         ++End[now];
34     }
35     void Build()
36     {
37         queue<int > que;
38         fail[root] = root;
39         FOR(i, 0, 26) {
40             if (next[root][i] == -1) next[root][i] = root;
41             else {
42                 fail[next[root][i]] = root;
43                 que.push(next[root][i]);
44             }
45         }
46         while (!que.empty()) {
47             int now = que.front();
48             que.pop();
49             FOR(i, 0, 26) {
50                 if (next[now][i] == -1) {
51                     next[now][i] = next[fail[now]][i];
52                 } else {
53                     fail[next[now][i]] = next[fail[now]][i];
54                     que.push(next[now][i]);
55                 }
56             }
57         }
58     }
59     int Query(char *str)
60     {
61         int len = strlen(str), now = root, res = 0;
62         FOR(i, 0, len) {
63             int id = str[i] - ‘a‘;
64             now = next[now][id];
65             int tmp = now;
66             while (tmp != root) {
67                 res += End[tmp];
68                 End[tmp] = 0;
69                 tmp = fail[tmp];
70             }
71         }
72         return res;
73     }
74 } AC;
75 
76 int n;
77 char str[1000000 + 100];
78 
79 int main()
80 {
81     int Cas;
82     scanf("%d", &Cas);
83     while (Cas--) {
84         AC.Init();
85         scanf("%d", &n);
86         REP(i, 1, n) {
87             scanf("%s", str);
88             AC.Insert(str);
89         }
90         AC.Build();
91         scanf("%s", str);
92         printf("%d\n", AC.Query(str));
93     }
94     return 0;
95 }
View Code

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2896

思路：和上题差不多，只是用End数组来记录序号而已。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <vector>
  7 #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  8 #define REP(i, a, b) for (int i = (a); i <= (b); ++i)
  9 using namespace std;
 10 
 11 const int MAX_N = (100000 + 1000);
 12 struct Trie {
 13 
 14     int next[MAX_N][128], End[MAX_N], fail[MAX_N];
 15     int root, L;
 16     int NewNode() {
 17         FOR(i, 0, 128) next[L][i] = -1;
 18         End[L++] = 0;
 19         return L - 1;
 20     }
 21     void Init() {
 22         L = 0;
 23         root = NewNode();
 24     }
 25 
 26     void Insert(char *str, int index) {
 27         int len = strlen(str), now = root;
 28         FOR(i, 0, len) {
 29             int id = str[i];
 30             if (next[now][id] == -1) next[now][id] = NewNode();
 31             now = next[now][id];
 32         }
 33         End[now] = index;
 34     }
 35     void Build() {
 36         queue<int > que;
 37         fail[root] = root;
 38         FOR(i, 0, 128) {
 39             if (next[root][i] == -1) next[root][i] = root;
 40             else {
 41                 fail[next[root][i]] = root;
 42                 que.push(next[root][i]);
 43             }
 44         }
 45         while (!que.empty()) {
 46             int now = que.front();
 47             que.pop();
 48             FOR(i, 0, 128) {
 49                 if (next[now][i] == -1) {
 50                     next[now][i] = next[fail[now]][i];
 51                 } else {
 52                     fail[next[now][i]] = next[fail[now]][i];
 53                     que.push(next[now][i]);
 54                 }
 55             }
 56         }
 57     }
 58     void Query(char *str, vector<int > &ans) {
 59         int len = strlen(str), now = root;
 60         FOR(i, 0, len) {
 61             now = next[now][str[i]];
 62             int tmp = now;
 63             while (tmp != root) {
 64                 if (End[tmp]) ans.push_back(End[tmp]);
 65                 tmp = fail[tmp];
 66             }
 67         }
 68     }
 69 
 70 } AC;
 71 
 72 int N, M, res;
 73 char str[10000 + 100];
 74 vector<int > ans[1000 + 100];
 75 
 76 int main()
 77 {
 78     AC.Init();
 79     scanf("%d", &N);
 80     REP(i, 1, N) {
 81         scanf("%s", str);
 82         AC.Insert(str, i);
 83     }
 84     AC.Build();
 85     scanf("%d", &M);
 86     FOR(i, 0, M) {
 87         scanf("%s", str);
 88         AC.Query(str, ans[i]);
 89     }
 90     res = 0;
 91     FOR(i, 0, M) {
 92         if ((int)ans[i].size()) {
 93             printf("web %d:", i + 1);
 94             sort(ans[i].begin(), ans[i].end());
 95             FOR(j, 0, (int)ans[i].size()) printf(" %d", ans[i][j]);
 96             puts("");
 97             ++res;
 98         }
 99     }
100     printf("total: %d\n", res);
101     return 0;
102 }
View Code

 

 

 

 


联系
我们