hdu 2222:Keywords Search

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<string.h>
 5 #include<queue>
 6 using namespace std;
 7 struct Trie{
 8     int next[500010][26],end[500010];//存储节点信息：
 9     //next[i][j]=k 表示第 i个节点，在第 j个字母的位置上有个节点 k
10     //end[i]=k 表示以 i节点结尾的单词有 k个 
11     int fail[500010];
12     int root,tot;//root表示根 tot表示总节点数 
13     int newnode(){//建立新节点 
14         for(int i=0;i<26;i++) next[tot][i]=-1;//新节点的儿子都是空 
15         end[tot++]=0;//下一个新节点的编号 
16         return tot-1;//返回当前新节点的编号 
17     }
18     void init(){//初始化，建立Trie的入口 
19         tot=0;
20         root=newnode();
21     }
22     void insert(char buf[]){//插入单词 
23         int len=strlen(buf);
24         int now=root;//now表示应当插入位置的父亲 
25         for(int i=0;i<len;i++){//算上原点，新单词插入深度为 1 ~ len 
26             if(next[now][buf[i]-‘a‘]==-1) next[now][buf[i]-‘a‘]=newnode();
27             now=next[now][buf[i]-‘a‘];
28         }
29         end[now]++;//以该节点为结尾的单词数量+1 
30     }
31     void build(){//建立fail指针 
32         queue<int> Q;
33         fail[root]=root;//根的fail指向根 
34         for(int i=0;i<26;i++){
35             if(next[root][i]==-1)//如果根的某些孩子为空，就把这些孩子看做根 
36                 next[root][i]=root;
37             else{//如果不为空，这些孩子的fail肯定指向根，并加入队列 
38                 fail[next[root][i]]=root;
39                 Q.push(next[root][i]);
40             }
41         }
42         while(!Q.empty()){
43             int now=Q.front(); Q.pop();
44             for(int i=0;i<26;i++){//利用已经确定fail指针的节点来更新 
45                 if(next[now][i]==-1)//now的某孩子为空，让这个孩子的编号改为 now的fail指向的节点的孩子，依次类推，如果都没子节点就会指向根  
46                     next[now][i]=next[fail[now]][i];
47                 else{
48                     fail[next[now][i]]=next[fail[now]][i];
49                     Q.push(next[now][i]);
50                 }
51             }
52         }
53     }
54     int query(char buf[]){//询问该串中出现了几个单词 
55         int len=strlen(buf),now=root;
56         int res=0;
57         for(int i=0;i<len;i++){
58             now=next[now][buf[i]-‘a‘];
59             int temp=now;
60             while(temp!=root){
61                 res+=end[temp];
62                 end[temp]=0;
63                 temp=fail[temp];
64             }
65         }
66         return res;
67     }
68 }ac;
69 char buf[1000010];
70 int T,n;
71 int main(){
72     scanf("%d",&T);
73     while(T--){
74         scanf("%d",&n);
75         ac.init();
76         for(int i=0;i<n;i++){
77             scanf("%s",buf);
78             ac.insert(buf);
79         }
80         ac.build();
81         scanf("%s",buf);
82         printf("%d\n",ac.query(buf));
83     }
84     return 0;
85 }