HDU 3065 病毒侵袭持续中（AC自动机）

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

题意：有n个模式串，一个主串，求每个模式串在主串中出现的次数

思路：AC自动机水题，trie树中也要维护标号，再开一个num数组记录出现次数即可，扫描匹配时注意跳转fail指针和root节点。

code：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <string>
  4 #include <queue>
  5 using namespace std;
  6 const int KIND = 26;
  7 struct node
  8 {
  9     int id;
 10     node* fail;
 11     node* next[KIND];
 12     node ()
 13     {
 14         id = 0;
 15         fail = NULL;
 16         for (int i = 0; i < KIND; ++i) next[i] = NULL;
 17     }
 18 };
 19 node* root;
 20 int L;
 21 char str[1005][55];
 22 char text[2000005];
 23 int num[1005];
 24 
 25 void Insert(char str[])
 26 {
 27     node* temp = root;
 28     int len = strlen(str);
 29     for (int i = 0; i < len; ++i)
 30     {
 31         int curr = str[i] - 'A';
 32         if (temp->next[curr] == NULL)
 33             temp->next[curr] = new node();
 34         temp = temp->next[curr];
 35     }
 36     temp->id = ++L;
 37 }
 38 
 39 void Build()
 40 {
 41     queue<node*> Q;
 42     root->fail = root;
 43     for (int i = 0; i < KIND; ++i)
 44     {
 45         if (root->next[i] == NULL)
 46             root->next[i] = root;
 47         else
 48         {
 49             root->next[i]->fail = root;
 50             Q.push(root->next[i]);
 51         }
 52     }
 53     while (!Q.empty())
 54     {
 55         node* temp = Q.front();
 56         Q.pop();
 57         for (int i = 0; i < KIND; ++i)
 58         {
 59             if (temp->next[i] == NULL)
 60                 temp->next[i] = temp->fail->next[i];
 61             else
 62             {
 63                 temp->next[i]->fail = temp->fail->next[i];
 64                 Q.push(temp->next[i]);
 65             }
 66         }
 67     }
 68 }
 69 
 70 void Query()
 71 {
 72     node* temp = root;
 73     int len = strlen(text);
 74     for (int i = 0; i < len; ++i)
 75     {
 76         if (text[i] < 'A' || text[i] > 'Z')
 77         {
 78             temp = root;
 79             continue;
 80         }
 81         int curr = text[i] - 'A';
 82         while (temp->next[curr] == NULL && temp != root) temp = temp->fail;
 83         temp = temp->next[curr];
 84         if (temp == NULL) temp = root;
 85         node* x = temp;
 86         while (x != root)
 87         {
 88             if (x->id != 0) ++num[x->id];
 89             x = x->fail;
 90         }
 91     }
 92 }
 93 
 94 int main()
 95 {
 96     int n;
 97     while (scanf("%d", &n) != EOF)
 98     {
 99         L = 0;
100         root = new node();
101         for (int i = 1; i <= n; ++i)
102         {
103             scanf("%s", str[i]);
104             Insert(str[i]);
105         }
106         Build();
107         scanf("%s", text);
108         memset(num, 0, sizeof(num));
109         Query();
110         for (int i = 1; i <= n; ++i)
111         {
112             if (num[i] == 0) continue;
113             printf("%s: %d
", str[i], num[i]);
114         }
115     }
116     return 0;
117 }

数组实现：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 const int KIND = 26;
  6 const int MAXN = 50005;
  7 const int MAXM = 2000005;
  8 
  9 struct Trie
 10 {
 11     int next[MAXN][KIND], fail[MAXN], id[MAXN], num[MAXN];
 12     int root, L, n;
 13     int create()
 14     {
 15         for (int i = 0; i < KIND; ++i)
 16             next[L][i] = -1;
 17         id[L++] = 0;
 18         return L - 1;
 19     }
 20     void init()
 21     {
 22         L = 0;
 23         n = 0;
 24         root = create();
 25         memset(num, 0, sizeof(num));
 26     }
 27     void insert(char str[])
 28     {
 29         int now = root;
 30         int len = strlen(str);
 31         for (int i = 0; i < len; ++i)
 32         {
 33             int curr = str[i] - 'A';
 34             if (-1 == next[now][curr])
 35                 next[now][curr] = create();
 36             now = next[now][curr];
 37         }
 38         id[now] = ++n;
 39     }
 40     void build()
 41     {
 42         queue<int>Q;
 43         fail[root] = root;
 44         for (int i = 0; i < KIND; ++i)
 45         {
 46             if (-1 == next[root][i])
 47                 next[root][i] = root;
 48             else
 49             {
 50                 fail[next[root][i]] = root;
 51                 Q.push(next[root][i]);
 52             }
 53         }
 54         while (!Q.empty())
 55         {
 56             int now = Q.front();
 57             Q.pop();
 58             for (int i = 0; i < KIND; ++i)
 59             {
 60                 if (-1 == next[now][i])
 61                     next[now][i] = next[fail[now]][i];
 62                 else
 63                 {
 64                     fail[next[now][i]] = next[fail[now]][i];
 65                     Q.push(next[now][i]);
 66                 }
 67             }
 68         }
 69     }
 70     void query(char str[])
 71     {
 72         int now = root;
 73         int len = strlen(str);
 74         for (int i = 0; i < len; ++i)
 75         {
 76             if (str[i] < 'A' || str[i] > 'Z')
 77             {
 78                 now = root;
 79                 continue;
 80             }
 81             now = next[now][str[i] - 'A'];
 82             int temp = now;
 83             while (temp != root)
 84             {
 85                 if (id[temp]) ++num[id[temp]];
 86                 temp = fail[temp];
 87             }
 88         }
 89     }
 90 };
 91 Trie ac;
 92 char str[1005][55];
 93 char text[MAXM];
 94 int main()
 95 {
 96     int n;
 97     while (scanf("%d", &n) != EOF)
 98     {
 99         ac.init();
100         for (int i = 1; i <= n; ++i)
101         {
102             scanf("%s", str[i]);
103             ac.insert(str[i]);
104         }
105         ac.build();
106         scanf("%s", text);
107         ac.query(text);
108         for (int i = 1; i <= n; ++i)
109         {
110             if (0 == ac.num[i]) continue;
111             printf("%s: %d
", str[i], ac.num[i]);
112         }
113     }
114     return 0;
115 }