HDU 2222 Keywords Search（AC自动机）

题目大意

给了 n(n<=10^4) 个单词，每个单词只包含 'a'~'z'，长度不超过 50。

最后给出一个字符串，长度不超过 10^6

问的是：这个字符串中，包含几个单词？

做法分析

先把所有的单词建成一颗字典树，然后求 fail 指针，做成自动机

最后，对读入的字符串进行匹配，注意，如果这个单词已经匹配过了，那么需要一个特殊的标记

参考代码

HDU 2222

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <queue>
  5 
  6 using namespace std;
  7 
  8 struct Node
  9 {
 10     Node *next[26], *fail;
 11     int cnt;
 12     void init()
 13     {
 14         for(int i=0; i<26; i++) next[i]=NULL;
 15         fail=NULL, cnt=0;
 16     }
 17 } mem[510006];
 18 int tot;
 19 
 20 void Insert(Node *root, char buff[])
 21 {
 22     Node *u=root;
 23     for(int i=0; buff[i]; i++)
 24     {
 25         int id=buff[i]-'a';
 26         if(u->next[id]==NULL)
 27         {
 28             mem[tot].init();
 29             u->next[id]=&mem[tot++];
 30         }
 31         u=u->next[id];
 32     }
 33     u->cnt++;
 34 }
 35 
 36 queue <Node*> Q;
 37 void getFail(Node *root)
 38 {
 39     root->fail=NULL;
 40     while(!Q.empty()) Q.pop();
 41     Q.push(root);
 42     while(!Q.empty())
 43     {
 44         Node *u=Q.front(), *v;
 45         Q.pop();
 46         for(int i=0; i<26; i++)
 47         {
 48             if(u->next[i]==NULL) continue;
 49             for(v=u->fail; v!=NULL; v=v->fail)
 50             {
 51                 if(v->next[i]==NULL) continue;
 52                 u->next[i]->fail=v->next[i];
 53                 break;
 54             }
 55             if(v==NULL) u->next[i]->fail=root;
 56             Q.push(u->next[i]);
 57         }
 58     }
 59 }
 60 
 61 int Find(Node *root, char buff[])
 62 {
 63     int sum=0;
 64     Node *u=root, *v;
 65     for(int i=0; buff[i]; i++)
 66     {
 67         int id=buff[i]-'a';
 68         while(u->next[id]==NULL && u!=root) u=u->fail;
 69         u=u->next[id]==NULL?root:u->next[id];
 70 
 71         for(v=u; v!=root && v->cnt!=-1; v=v->fail)
 72         {
 73             sum+=v->cnt;
 74             v->cnt=-1;
 75         }
 76     }
 77     return sum;
 78 }
 79 
 80 int n, t;
 81 char buff[1000006];
 82 
 83 int main()
 84 {
 85     scanf("%d", &t);
 86     for(int ca=1; ca<=t; ca++)
 87     {
 88         mem[tot=0].init();
 89         Node *root=&mem[tot++];
 90         scanf("%d", &n);
 91         for(int i=0; i<n; i++)
 92         {
 93             scanf("%s", buff);
 94             Insert(root, buff);
 95         }
 96         getFail(root);
 97         scanf("%s", buff);
 98         printf("%d\n", Find(root, buff));
 99     }
100     return 0;
101 }

AC通道

HDU 2222 Keywords Search