HDU 2896 病毒侵袭（AC自动机）

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

题意：给你n个模式串，m个主串，求出每个主串中出现的模式串的标号。

思路：AC自动机水题，trie树中维护标号，m次扫描即可，注意点输出格式。

code：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <set>
  5 using namespace std;
  6 const int MAXN = 10005;
  7 const int KIND = 128;
  8 
  9 struct node
 10 {
 11     int id;
 12     node* fail;
 13     node* next[KIND];
 14     node()
 15     {
 16         id = 0;
 17         fail = NULL;
 18         for (int i = 0; i < KIND; ++i) next[i] = NULL;
 19     }
 20 };
 21 node* root;
 22 int L = 0;
 23 char str[MAXN];
 24 set<int> ans;
 25 
 26 void Insert(char str[])
 27 {
 28     node* temp = root;
 29     int len = strlen(str);
 30     for (int i = 0; i < len; ++i)
 31     {
 32         if (temp->next[str[i]] == NULL)
 33             temp->next[str[i]] = new node();
 34         temp = temp->next[str[i]];
 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 int Query(char str[])
 71 {
 72     node* temp = root;
 73     int len = strlen(str);
 74     ans.clear();
 75     for (int i = 0; i < len; ++i)
 76     {
 77         while (temp->next[str[i]] == NULL && temp != root) temp = temp->fail;
 78         temp = temp->next[str[i]];
 79         if (temp == NULL) temp = root;
 80         node* x = temp;
 81         while (x != root)
 82         {
 83             if (x->id != 0) ans.insert(x->id);
 84             x = x->fail;
 85         }
 86     }
 87     return ans.size();
 88 }
 89 
 90 
 91 int main()
 92 {
 93     int n, m;
 94     int tot = 0;
 95     while (scanf("%d", &n) != EOF)
 96     {
 97         root = new node();
 98         for (int i = 0; i < n; ++i)
 99         {
100             scanf("%s", str);
101             Insert(str);
102         }
103         Build();
104         scanf("%d", &m);
105         for (int i = 1; i <= m; ++i)
106         {
107             scanf("%s", str);
108             int num = Query(str);
109             if (num == 0) continue;
110             printf("web %d:", i);
111             set<int>::iterator it;
112             for (it = ans.begin(); it != ans.end(); ++it) printf(" %d", *it);
113             printf("
");
114             ++tot;
115         }
116         printf("total: %d
", tot);
117     }
118     return 0;
119 }

数组实现：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <set>
  5 using namespace std;
  6 const int KIND = 128;
  7 const int MAXN = 100005;
  8 const int MAXM = 10005;
  9 
 10 struct Trie
 11 {
 12     int next[MAXN][KIND], fail[MAXN], id[MAXN];
 13     int root, L, num;
 14     set<int> ans;
 15     int create()
 16     {
 17         for (int i = 0; i < KIND; ++i)
 18             next[L][i] = -1;
 19         id[L++] = 0;
 20         return L - 1;
 21     }
 22     void init()
 23     {
 24         num = 0;
 25         L = 0;
 26         root = create();
 27     }
 28     void insert(char str[])
 29     {
 30         int now = root;
 31         int len = strlen(str);
 32         for (int i = 0; i < len; ++i)
 33         {
 34             if (-1 == next[now][str[i]])
 35                 next[now][str[i]] = create();
 36             now = next[now][str[i]];
 37         }
 38         id[now] = ++num;
 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     int query(char str[])
 71     {
 72         ans.clear();
 73         int now = root;
 74         int len = strlen(str);
 75         for (int i = 0; i < len; ++i)
 76         {
 77             now = next[now][str[i]];
 78             int temp = now;
 79             while (temp != root)
 80             {
 81                 if (id[temp]) ans.insert(id[temp]);
 82                 temp = fail[temp];
 83             }
 84         }
 85         return (int)ans.size();
 86     }
 87 };
 88 Trie ac;
 89 char str[MAXM];
 90 int main()
 91 {
 92     int n, m, tot;
 93     while (scanf("%d", &n) != EOF)
 94     {
 95         ac.init();
 96         tot = 0;
 97         for (int i = 0; i < n; ++i)
 98         {
 99             scanf("%s", str);
100             ac.insert(str);
101         }
102         ac.build();
103         scanf("%d", &m);
104         for (int i = 1; i <= m; ++i)
105         {
106             scanf("%s", str);
107             if (0 == ac.query(str)) continue;
108             printf("web %d:", i);
109             set<int>::iterator it;
110             for (it = ac.ans.begin(); it != ac.ans.end(); ++it) printf(" %d", *it);
111             printf("
");
112             ++tot;
113         }
114         printf("total: %d
", tot);
115     }
116     return 0;
117 }