首页 > 代码库 > [HDOJ2222]Keywords Search（AC自动机）

[HDOJ2222]Keywords Search（AC自动机）

2024-09-14 11:19:37   217人阅读

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

题意：求字典中所有模式串各出现了多少次。

建立AC自动机，查询的时候首先跳过所有cur->next[index]为NULL的情况，再跳过cur是root的情况。因为root不存任何信息。

过滤完上述情况，那么当前匹配串上的index位置必然在trie上出现过，那么就沿着当前点的fail一路找上去。因为trie某节点的fail指针要么指向root，要么指向与当前字符相同的节点。接着记下每个点的cnt值，不要忘记置零防止重复统计。

时隔多年（什么多年啊喂）重拾AC自动机，终于彻彻底底弄明白了。感恩的心。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 inline int GetId(char c) {
  5     return c - ‘a‘;
  6 }
  7 typedef class Node {
  8 public:
  9     Node *next[26];
 10     Node *fail;
 11     int cnt;
 12     Node() {
 13         memset(next, 0, sizeof(next));
 14         fail = NULL;
 15         cnt = 0;
 16     }
 17 }Node;
 18 class AC_Automation {
 19 public:
 20     Node *root;
 21     queue <Node*> q;
 22     AC_Automation() {
 23         root = new Node;
 24         while(!q.empty()) q.pop();
 25     }
 26     void insert(string s) {
 27         Node *cur = root;
 28         int len = s.length();
 29         for(int i = 0; i < len; i++) {
 30             int index = GetId(s[i]);
 31             if(cur->next[index] == NULL) {
 32                 cur->next[index] = new Node;
 33             }
 34             cur = cur->next[index];
 35         }
 36         cur->cnt++;
 37     }
 38     void BuildAC() {
 39         Node *cur,*tmp;
 40         q.push(root);
 41         while(!q.empty()) {
 42             cur = q.front();
 43             q.pop();
 44             for(int i = 0; i < 26; i++) {
 45                 if(cur->next[i]) {
 46                     if(cur == root) {
 47                         cur->next[i]->fail = root;
 48                     }
 49                     else {
 50                         tmp = cur->fail;
 51                         while(tmp != NULL) {
 52                             if(tmp->next[i]) {
 53                                 cur->next[i]->fail = tmp->next[i];
 54                                 break;
 55                             }
 56                             tmp = tmp->fail;
 57                         } 
 58                         if(tmp == NULL) {
 59                             cur->next[i]->fail = root;
 60                         }
 61                     }
 62                     q.push(cur->next[i]);
 63                 }
 64             }
 65         }
 66     }
 67     int query(string s) {
 68         Node *cur = root,*tmp;
 69         int len = s.length();
 70         int ret = 0;
 71         for(int i = 0; i < len; i++) {
 72             int index = GetId(s[i]);
 73             while(cur->next[index] == NULL && cur != root) {
 74                 cur = cur->fail;
 75             }
 76             cur = cur->next[index];
 77             if(cur == NULL) {
 78                 cur = root;
 79                 continue;
 80             }
 81             tmp = cur;
 82             while(tmp != root) {
 83                 ret += tmp->cnt;
 84                 tmp->cnt = 0;
 85                 tmp = tmp->fail;
 86             }
 87         }
 88         return ret;
 89     }
 90 };
 91 char pat[52], tar[2000005];
 92 int n;
 93 
 94 int main() {
 95     // freopen("in", "r", stdin);
 96     int T;
 97     scanf("%d", &T);
 98     while(T--) {
 99         scanf("%d", &n);
100         AC_Automation ac;
101         for(int i = 0; i < n; i++) {
102             scanf("%s", pat);
103             ac.insert(pat);
104         }
105         ac.BuildAC();
106         scanf("%s", tar);
107         cout << ac.query(tar) << endl;
108     }
109     return 0;
110 }

 

[HDOJ2222]Keywords Search（AC自动机）


联系
我们