题意:给你n个单词,再给你一串字符,求在字符中有多少个单词出现过

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 10010
#define MAXLEN 1000010
struct node{
node *child[26];
node *fail;
int count;
void init(){
for(int i=0;i<26;i++)
child[i]=NULL;
count=0;
fail=NULL;
}
}*q[50*N];
node *root;
int head,tail;
void insert(char *str){//构建前缀树
node *now,*next;
int i=0,t;
now=root;
while(str[i]){
t=str[i]-'a';
if(now->child[t]!=NULL)
now=now->child[t];
else{
next=new node;
next->init();
now->child[t]=next;
now=next;
}
i++;
}
now->count++;
}
void build_fail(){
int i;
node *now,*p;
head=tail=0;
now=root;
q[tail++]=now;
while(head<tail){
now=q[head];
for(i=0;i<26;i++){
if(now->child[i]==NULL) continue;
if(now==root) now->child[i]->fail=root;
else{
p=now->fail;
while(p!=NULL){
if(p->child[i]!=NULL){
now->child[i]->fail=p->child[i];
break;
}
p=p->fail;
}
if(p==NULL) now->child[i]->fail=root;
}
q[tail++]=now->child[i];
}
head++;
}
}
int query(char *str){
node *now,*temp;
int i,t,cnt;
i=cnt=0;
now=root;
while(str[i]){
t=str[i]-'a';
while(now->child[t]==NULL&&now!=root) now=now->fail;
now=now->child[t];
if(now==NULL) now=root;
temp=now;
while(temp!=NULL&&temp->count!=-1){
cnt+=temp->count;
temp->count=-1;
temp=temp->fail;
}
i++;
}
return cnt;
}
int main(int argc, char** argv) {
int t,n;
char str[MAXLEN];
scanf("%d",&t);
while(t--){
scanf("%d",&n);
root=new node;
root->init();
while(n--){
scanf("%s",str);
insert(str);
}
build_fail();
scanf("%s",str);
printf("%d\n",query(str));
}
return 0;
}
04-30 04:12