31 string s, a[51]; 32 int head, tail; 33  34 struct node { 35     node *fail; 36     node *next[26]; 37     int count; 38     node() { 39         fail = NULL; 40         count = 0; 41         rep(i, 0, 26) next[i] = NULL; 42     } 43 }*q[MAXN]; 44 node *root; 45  46 void insert(string s) { 47     node *p = root; 48     int len = s.length(); 49     rep(i, 0, len) { 50         int temp = s[i] - ‘a‘; 51         if (p->next[temp] == NULL) p->next[temp] = new node(); 52         p = p->next[temp]; 53     } 54     p->count++; 55 } 56  57 void build_ac() { 58     q[tail++] = root; 59     while (head != tail) { 60         node *p = q[head++]; 61         node *temp = NULL; 62         rep(i, 0, 26) if (p->next[i] != NULL) { 63             if (p == root) p->next[i]->fail = root; 64             else { 65                 temp = p->fail; 66                 while (temp != NULL) { 67                     if (temp->next[i] != NULL) { 68                         p->next[i]->fail = temp->next[i]; 69                         break; 70                     } 71                     temp = temp->fail; 72                 } 73                 if (temp == NULL) p->next[i]->fail = root; 74             } 75             q[tail++] = p->next[i]; 76         } 77     } 78 } 79  80 int query() { 81     int res = 0; 82     node *p = root; 83     int len = s.length(); 84     rep(i, 0, len) { 85         int index = s[i] - ‘a‘; 86         while (p->next[index] == NULL && p != root) p = p->fail; 87         p = p->next[index]; 88         if (p == NULL) p = root; 89         node *temp = p; 90         while (temp != root && temp->count != -1) { 91             res += temp->count; 92             temp->count = -1; 93             temp = temp->fail; 94          } 95     } 96     return res; 97 } 98  99 int main() {100     ios::sync_with_stdio(false), cin.tie(0);101     int T;102     cin >> T;103     while (T--) {104         head = tail = 0;105         root = new node();106         int n;107         cin >> n;108         while (n--) {109             cin >> s;110             insert(s);111         }112         build_ac();113         cin >> s;114         cout << query() << endl;115     }116     return 0;117 }