|
|
 #include <iostream>
using namespace std;
const int MAXN=50*10005;
const int MAXL=1005;
const int K=26;
struct Node
   {
 Node *next[K], *fail;
int flag, id;
void Init(int index)
  {
id=index;
flag=0;
fail=NULL;
for(int i=0; i<K; i++)next[i]=NULL;
 }
 }* Q[MAXN/2], *root, T[MAXN];// Q for queue, root&T for tree;
int index=0;
Node * newNode()
{
T[index].Init(index);
return &T[index++];
}
int tokind(char k){return k-'a';}
void insert(char *str)
{
if(root==NULL)
root=newNode();
Node *now=root;
for(int i=0; str[i]; i++)
{
int kind=tokind(str[i]);
if(now->next[kind]==NULL)
now->next[kind]=newNode();
now=now->next[kind];
}
now->flag++;
}
void buildAC()
{
int head=0, tail=0;
root->fail=NULL;
Q[tail++]=root;
while(head<tail)
{
Node *now=Q[head++];
for(int i=0; i<K; i++)
{
if(now->next[i]!=NULL)
{
if(now==root)now->next[i]->fail=root;
else
{
Node *p=now->fail;
while(p->next[i]==NULL&&p!=root)p=p->fail;
p=p->next[i];
now->next[i]->fail=(p==NULL)?root:p;
}
Q[tail++]=now->next[i];
}
}
}
}
int query(char *str)
{
int res=0;
Node *p=root;
for(int i=0; str[i]; i++)
{
int kind=tokind(str[i]);
while(p->next[kind]==NULL&&p!=root)p=p->fail;
p=p->next[kind];
p=(p==NULL)?root:p;
Node *now=p;
while(now!=root&&now->flag!=-1)
{
res+=now->flag;
now->flag=-1;
now=now->fail;
}
}
return res;
}
int main()
{
//freopen ("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while(T--)
{
int n;
root=NULL;
scanf("%d",&n);getchar();
while(n--)
{
char str[55];
scanf("%s",str);
insert(str);
}
buildAC();
char ch[1000005];
scanf("%s",ch);
printf("%d\n",query(ch));
}
return 0;
}
|