1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <queue>  6 using namespace std;  7   8 #define MAXL  1000005  9 #define TRIEN 26 10  11 char des[MAXL], src[55]; 12  13 typedef struct Trie { 14     int n; 15     Trie *fail; 16     Trie *next[TRIEN]; 17     Trie () { 18         n = 0; 19         fail = NULL; 20         memset(next, 0, sizeof(next)); 21     } 22 } Trie; 23  24 Trie *root; 25 int n; 26  27 void create(char str[]) { 28     int i=0, id; 29     Trie *p = root, *q; 30  31     while (str[i]) { 32         id = str[i] - ‘a‘; 33         ++i; 34         if (p->next[id] == NULL) { 35             q = new Trie(); 36             p->next[id] = q; 37         } 38         p = p->next[id]; 39     } 40     p->n++; 41 } 42  43 void build_fail() { 44     int i; 45     Trie *p, *q; 46     queue<Trie *> que; 47  48     for (i=0; i<TRIEN; ++i) { 49         if (root->next[i]) { 50             root->next[i]->fail = root; 51             que.push(root->next[i]); 52         } 53     } 54  55     while (!que.empty()) { 56         p = que.front(); 57         que.pop(); 58         for (i=0; i<TRIEN; ++i) { 59             if (p->next[i]) { 60                 q = p->fail; 61                 while (q != NULL) { 62                     if (q->next[i]) { 63                         p->next[i]->fail = q->next[i]; 64                         break; 65                     } 66                     q = q->fail; 67                 } 68                 if (q == NULL) 69                     p->next[i]->fail = root; 70                 que.push(p->next[i]); 71             } 72         } 73     } 74 } 75  76 void search() { 77     int i = 0, id; 78     Trie *p = root, *tmp; 79  80     n = 0; 81  82     while (des[i]) { 83         id = des[i] - ‘a‘; 84         ++i; 85         while (p->next[id]==NULL && p!=root) 86             p = p->fail; 87         p = p->next[id]; 88         if (p == NULL) 89             p = root; 90         tmp = p; 91         while (tmp != root) { 92             n += tmp->n; 93             tmp->n = 0; 94             tmp = tmp->fail; 95         } 96     } 97 } 98  99 void del(Trie *t) {100     if (t == NULL)101         return ;102     for (int i=0; i<TRIEN; ++i)103         del(t->next[i]);104     free(t);105 }106 107 int main() {108     int case_n;109 110     scanf("%d", &case_n);111     while (case_n--) {112         scanf("%d", &n);113         root = new Trie();114         while (n--) {115             scanf("%s", src);116             create(src);117         }118         scanf("%s", des);119         build_fail();120         search();121         printf("%d\n", n);122         del(root);123     }124 125     return 0;126 }