貌似理解还不是很深。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
struct node
{
int cnt;
node *next[27],*fail;
node():cnt(0)
{
memset(next,0,sizeof(next));
fail=0;
}
};
char str[1000005];
node *root;
void insert(char *str)
{
int l=strlen(str);
node * p=root;
int i;
for(i=0;i<l;i++)
{
if(p->next[str[i]-'a']==0)
{
p->next[str[i]-'a']=new node;
}
p=p->next[str[i]-'a'];
}
p->cnt++;
}
void build_fail()
{
queue<node *> q;
node *p=root;
p->fail=0;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
int i;
for(i=0;i<26;i++)
{
if(p->next[i])
{
node *temp=p->fail;
while(temp)
{
if(temp->next[i])
{
p->next[i]->fail=temp->next[i];
break;
}
temp=temp->fail;
}
if(temp==0)
p->next[i]->fail=root;
q.push(p->next[i]);
}
}
}
}
int ac_find(char *str)
{
int l=strlen(str);
int i;
int cnt=0;
node *p=root;
for(i=0;i<l;i++)
{
int k=str[i]-'a';
while(p!=root&&p->next[k]==0)
p=p->fail;
p=p->next[k]==0?root:p->next[k];
node *temp=p;
while(temp!=root&&temp->cnt!=-1)
{
cnt+=temp->cnt;
temp->cnt=-1;
temp=temp->fail;
}
}
return cnt;
}
char a[100];
int main()
{
int c;
scanf("%d",&c);
while(c--)
{
int n;
root=new node;
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
scanf("%s",a);
insert(a);
}
scanf("%s",str);
build_fail();
int s=ac_find(str);
printf("%d\n",s);
}
return 0;
}