[hdu2222] [AC自动机模板] Keywords Search [AC自动机]

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <cstdlib>
 8 #include <queue>
 9 
10 using namespace std;
11 
12 int    cnt;
13 int    ch[1100000][26],Fail[1100000],lab[1100000];
14 char    str[1100000],S[1100000];
15 
16 void    Add(const char * s)
17 {
18     int    p=0,i;
19     for(i=1;s[i];++i)
20     {
21         if(!ch[p][s[i]-97])ch[p][s[i]-97]=++cnt;
22         p=ch[p][s[i]-97];
23     }
24     lab[p]++;
25     return ;
26 }
27 
28 void    Build()
29 {
30     int    i,t;
31     queue<int>    Q;
32     Q.push(0);
33     while(!Q.empty())
34     {
35         t=Q.front();Q.pop();
36         for(i=0;i<26;++i)
37         {
38             if(ch[t][i])
39             {
40                 Q.push(ch[t][i]);
41                 Fail[ch[t][i]]=t?ch[Fail[t]][i]:0;
42             }
43             else    ch[t][i]=ch[Fail[t]][i];
44         }
45     }
46     return ;
47 }
48 
49 int main()
50 {
51     int    T,n,i;
52 
53     scanf("%d",&T);
54     while(T--)
55     {
56         memset(Fail,0,sizeof(Fail));
57         memset(ch,0,sizeof(ch));
58         memset(lab,0,sizeof(lab));
59         cnt=0;
60         scanf("%d",&n);
61         for(i=1;i<=n;++i)
62         {
63             scanf("%s",str+1);
64             Add(str);
65         }
66         Build();
67         scanf("%s",S+1);
68         int    p=0,Ans=0;
69         for(i=1;S[i];++i)
70         {
71             p=ch[p][S[i]-97];
72             if(lab[p])
73             {
74                 int    pp=p;
75                 while(pp)Ans+=lab[pp],lab[pp]=0,pp=Fail[pp];
76             }
77         }
78         printf("%d\n",Ans);
79     }
80 
81     return 0;
82 }