1  /**//*hdu2222*/
2 #include<iostream>
3#include<algorithm>
4#include<map>
5using namespace std;
6
7const int MAXQ=500000+10;
8const int MAXN = 1000000+10;
9class trie
10 {
11 public:
12 trie *next[26];
13 trie *fail;
14 int count;
15 trie()
16  {
17 for(int i=0;i<26;i++)
18 next[i]=NULL;
19 count=0;
20 }
21 };
22trie *root;
23trie *q[MAXQ];
24char text[MAXN];
25void insert(char *s)
26{
27 int i,index;
28 trie *now=root;
29 i=0;
30 while(s[i]!='\0')
31 {
32 index=s[i]-'a';
33 if(now->next[index]==NULL)
34 now->next[index]=new trie;
35 now=now->next[index];
36 i++;
37 }
38 now->count++;
39}
40void build_AC_automation()
41{
42 trie *p,*now;
43 int top=0,tail=1;
44 q[0]=root;
45 root->fail=NULL;
46 while(top<tail)
47 {
48 now=q[top++];
49 for(int i=0;i<26;i++)
50 if(now->next[i]!=NULL)
51 {
52 if(now==root)
53 now->next[i]->fail=root;
54 else
55 {
56 p=now->fail;
57 while(p!=NULL)
58 {
59 if(p->next[i]!=NULL)
60 {
61 now->next[i]->fail=p->next[i];
62 break;
63 }
64 p=p->fail;
65 }
66 if(p==NULL)
67 now->next[i]->fail=root;
68 }
69 q[tail++]=now->next[i];
70 }
71 }
72}
73int AC_search()
74{
75 trie *cur=root,*p;
76 int index,ans;
77 ans=0;
78 for(int i=0;text[i]!='\0';i++)
79 {
80 index=text[i]-'a';
81 while(cur->next[index]==NULL && cur!=root)
82 cur=cur->fail;
83 cur=cur->next[index];
84 if(cur==NULL)
85 cur=root;
86 p=cur;
87 while(p!=NULL && p->count!=-1)
88 {
89 ans+=p->count;
90 p->count=-1;
91 p=p->fail;
92 }
93 }
94 return ans;
95}
96int main()
97{
98 int t,n;
99 char keyword[52];
100 scanf("%d",&t);
101 while(t--)
102 {
103 root=new trie();
104 scanf("%d",&n);
105 while(n--)
106 {
107 scanf("%s",keyword);
108 insert(keyword);
109 }
110
111 scanf("%s",text);
112 build_AC_automation();
113 printf("%d\n",AC_search());
114 }
115}
116
|