1 #include <stdio.h>  2 #include <algorithm>  3 #include <iostream>  4 #include <string.h>  5 #include <queue>  6 using namespace std;  7   8 struct Trie  9 { 10     int next[500010][26],fail[500010],end[500010]; 11     int root,L; 12     int newnode() 13     { 14         for(int i = 0;i < 26;i++) 15             next[L][i] = -1; 16         end[L++] = 0; 17         return L-1; 18     } 19     void init() 20     { 21         L = 0; 22         root = newnode(); 23     } 24     void insert(char buf[]) 25     { 26         int len = strlen(buf); 27         int now = root; 28         for(int i = 0;i < len;i++) 29         { 30             if(next[now][buf[i]-‘a‘] == -1) 31                 next[now][buf[i]-‘a‘] = newnode(); 32             now = next[now][buf[i]-‘a‘]; 33         } 34         end[now]++; 35     } 36     void build() 37     { 38         queue<int>Q; 39         fail[root] = root; 40         for(int i = 0;i < 26;i++) 41             if(next[root][i] == -1) 42                 next[root][i] = root; 43             else 44             { 45                 fail[next[root][i]] = root; 46                 Q.push(next[root][i]); 47             } 48         while( !Q.empty() ) 49         { 50             int now = Q.front(); 51             Q.pop(); 52             for(int i = 0;i < 26;i++) 53                 if(next[now][i] == -1) 54                     next[now][i] = next[fail[now]][i]; 55                 else 56                 { 57                     fail[next[now][i]]=next[fail[now]][i]; 58                     Q.push(next[now][i]); 59                 } 60         } 61     } 62     int query(char buf[]) 63     { 64         int len = strlen(buf); 65         int now = root; 66         int res = 0; 67         for(int i = 0;i < len;i++) 68         { 69             now = next[now][buf[i]-‘a‘]; 70             int temp = now; 71             while( temp != root ) 72             { 73                 res += end[temp]; 74                 end[temp] = 0; 75                 temp = fail[temp]; 76             } 77         } 78         return res; 79     } 80     void debug() 81     { 82         for(int i = 0;i < L;i++) 83         { 84             printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]); 85             for(int j = 0;j < 26;j++) 86                 printf("%2d",next[i][j]); 87             printf("]\n"); 88         } 89     } 90 }; 91 char buf[1000010]; 92 Trie ac; 93 int main() 94 { 95     int T; 96     int n; 97     scanf("%d",&T); 98     while( T-- ) 99     {100         scanf("%d",&n);101         ac.init();102         for(int i = 0;i < n;i++)103         {104             scanf("%s",buf);105             ac.insert(buf);106         }107         ac.build();108         scanf("%s",buf);109         printf("%d\n",ac.query(buf));110     }111     return 0;112 }