Keywords Search

  1 #include <stdio.h>  2 #include <queue>  3 #include <cstring>  4 #include <algorithm>  5 using namespace std;  6 const int maxn = 500010;  7 int ch[maxn][26];  8 char str[1000010];  9  10 struct ACAutomation 11 { 12      int ch[maxn][26],fail[maxn],val[maxn],last[maxn],sz,root; 13  14      int newnode()//新建一个节点 15      { 16          memset(ch[sz],0,sizeof(ch[sz]));//把这个节点的26个儿子置为0 17          val[sz]=0;//单词结尾标志 18          return sz++; 19      } 20  21      void init() 22      { 23          sz=0; 24          root = newnode(); 25      } 26  27      void insert() 28      { 29          int len = strlen(str); 30          int now = root; 31          for(int i=0;i<len;i++)//对每一位进行找到对应的节点 32          { 33              int &tmp = ch[now][str[i]-‘a‘];//now的儿子节点str[i]是否存在 34              if(tmp==0) 35                 tmp=newnode();//tmp=sz; 36              now = tmp; 37          } 38          val[now]++;//单词结束标记 39      } 40  41      void getfail() 42      { 43          queue<int> q; 44          fail[root] = root;//根节点的失败节点为它本身 45           for(int i = 0;i < 26;i++) 46           { 47                 int u = ch[root][i]; 48                 if(u!=0)//根节点的子节点的失败节点为root 49                 { 50                     fail[u] = last[u] = 0; 51                     q.push(u); 52                 } 53           } 54             while(!q.empty()) 55             { 56                 int now = q.front(); 57                 q.pop(); 58                 for(int i = 0;i < 26;i++) 59                 { 60                     int u = ch[now][i];//当前节点A 61                     if(!u) 62                         ch[now][i] = ch[fail[now]][i];//fail[now]就相当于我们说的父节点的失败节点C 63                         //当前节点now没有i这个儿子u，直接让这个点的第i个儿子u指向now的失败节点的第i个儿子 64                     else 65                     { 66                         fail[u] = ch[fail[now]][i]; 67                         //如果当前节点now有i这个儿子u，那么u的失败节点显然要指向C(即fail[now])的第i个儿子 68                         last[u] = val[fail[u]] ? fail[u]:last[fail[u]]; 69                         //沿着u的失配指针走遇到的下一个单词节点的 节点的编号。 70                         q.push(u); 71                     } 72                 } 73             } 74  75         } 76  77         int query() 78         { 79             int len = strlen(str); 80             int now = root; 81             int ret = 0; 82             for(int i = 0;i < len;i++) 83             { 84                 now = ch[now][str[i]-‘a‘]; 85                 int tmp = now; 86                 while(tmp != root && val[tmp]) 87                 { 88                     ret += val[tmp]; 89                     val[tmp] = 0; 90                     //统计完了之后，记得修改标记，以免再次统计 91                     tmp = last[tmp]; 92                     //对于在AC自动机走过的每一个单词节点，我们都要沿着后缀链接追踪，如果后缀链接指向的点是单词节点的话，这个点一定不能忘记统计。 93                 } 94             } 95             return ret; 96         } 97 }ac; 98  99 100 int main(){101     int t,n;102     scanf("%d",&t);103     while(t--){104         ac.init();105         scanf("%d",&n);106         for(int i = 0;i < n;i++){107             scanf("%s",str);108             ac.insert();109         }110         ac.getfail();111         scanf("%s",str);112         printf("%d\n",ac.query());113     }114     return 0;115 }