1 /*  2 1.对n个字符串构造tire树                        insertWord(node *root, char *word);  3 2.bfs构造fail指针                    makeFail(node *root);  4 3.基于以上两点的查询                query(node *root, char *str);  5 */  6 #include <stdio.h>  7 #include <string.h>  8 #include <queue>  9 using namespace std; 10 const int N1 = 50 + 10; 11 const int N2 = 1000000 + 10; 12 char key[N1]; 13 char desc[N2]; 14 struct node 15 { 16     node *next[26]; 17     int cnt; 18     node *fail; 19     node(){for(int i=0; i<26; ++i) next[i] = NULL; fail = NULL; cnt = 0;} 20 }; 21 void insertWord(node *root)//构造trie树 22 { 23     node *cur = root; 24     int n = strlen(key); 25     for(int i=0; i<n; ++i) 26     { 27         int index = key[i] - ‘a‘; 28         if(cur->next[index] != NULL) 29             cur = cur->next[index]; 30         else 31         { 32             cur->next[index] = new node(); 33             cur = cur->next[index]; 34         } 35     } 36     cur->cnt++; 37 } 38 void makeFail(node *root)//构造fail指针 39 { 40     queue<node*> q; 41     q.push(root); 42     node *cur; 43     while(!q.empty()) 44     {     45         cur = q.front(); 46         q.pop(); 47         for(int i=0; i<26; ++i) 48         { 49             if(cur->next[i] != NULL) 50             { 51                 if(cur == root)//与root相连的结点，即第二层的结点的fail指针都是root 52                     cur->next[i]->fail = root; 53                 else 54                 { 55                     node *tmp = cur; 56                     while(tmp->fail != NULL)// why while? 57                     { 58                         if(tmp->fail->next[i] != NULL) 59                         { 60                             cur->next[i]->fail = tmp->fail->next[i]; 61                             break; 62                         }                             63                         tmp = tmp->fail; 64                     } 65                     if(tmp->fail == NULL) 66                         cur->next[i]->fail = root; 67                 } 68                 q.push(cur->next[i]); 69             } 70         } 71     } 72 } 73 int query(node *root)//查询 74 { 75     node *cur = root; 76     node *tmp = NULL; 77     int i=0,cnt=0; 78     while(desc[i]) 79     { 80         int index = desc[i] - ‘a‘; 81         while(cur!=root && cur->next[index] == NULL) 82             cur = cur->fail; 83         if(cur->next[index] != NULL) 84         { 85             cur = cur->next[index]; 86             tmp = cur; 87             while(tmp != root && tmp->cnt!=0) 88             { 89                 cnt += tmp->cnt; 90                 tmp->cnt = 0; 91                 tmp = tmp->fail; 92             } 93         } 94         i++; 95     } 96     return cnt; 97 } 98 int main() 99 {100     int t,n;101     scanf("%d",&t);102     while(t--)103     {104         node *root = new node();105         scanf("%d",&n);106         for(int i=0; i<n; ++i)107         {108             scanf("%s",key);109             insertWord(root);110         }111         makeFail(root);112         scanf("%s",desc);113         int ans = query(root);114         printf("%d\n",ans);115     }116     return 0;117 }