1 #include<cstdio>  2 #include<cstring>  3 #include<queue>  4 #include<algorithm>  5 using namespace std;  6 const int Nmax=1000005;  7 const int Totmax=500005;  8 struct Aho  9 { 10     struct State 11     { 12         int next[26]; 13         int cnt,fail; 14     }state_table[Totmax]; 15  16     int size; 17     queue<int> Q; 18     void init() 19     { 20         while(Q.size()) 21             Q.pop(); 22         for(int i=0;i<Totmax;i++) 23         { 24             for(int j=0;j<26;j++)                 25                 state_table[i].next[j]=-1; 26             state_table[i].fail=state_table[i].cnt=0; 27         } 28         size=1; 29     } 30  31     void insert(char *s) 32     { 33         int n=strlen(s); 34         int now=0; 35         for(int i=0;i<n;i++) 36         { 37             char c=s[i]; 38             if(state_table[now].next[c-‘a‘]==-1) 39                 state_table[now].next[c-‘a‘]=size++; 40             now=state_table[now].next[c-‘a‘]; 41         } 42         state_table[now].cnt++; 43     } 44  45     void build() 46     { 47         Q.push(0); 48         state_table[0].fail=0; 49         while(Q.size()) 50         { 51             int now=Q.front(); 52             Q.pop(); 53             for(int i=0;i<26;i++) 54             { 55                 if(now==0) 56                 { 57                     if(state_table[now].next[i]==-1) 58                         state_table[now].next[i]=0; 59                     else 60                     { 61                         state_table[ state_table[now].next[i] ].fail=0; 62                         Q.push(state_table[now].next[i]); 63                     } 64                 } 65                 else 66                 { 67                     if(state_table[now].next[i]==-1) 68                     { 69                         state_table[now].next[i]=state_table[ state_table[now].fail ].next[i];  70                     }     71                     else 72                     { 73                         state_table[ state_table[now].next[i] ].fail=state_table[ state_table[now].fail ].next[i]; 74                         Q.push(state_table[now].next[i]); 75                     } 76                 } 77                  78             } 79         } 80     } 81  82     int match(char *s) 83     { 84         int n=strlen(s); 85         int ans=0; 86         int now=0; 87         for(int i=0;i<n;i++) 88         { 89             char c=s[i]; 90             now=state_table[now].next[c-‘a‘]; 91             if(state_table[now].cnt) 92             { 93                 int u=now; 94                 while(u) 95                 { 96                     ans+=state_table[u].cnt; 97                     state_table[u].cnt=0; 98                     u=state_table[u].fail; 99                 }100             }101         }102         return ans;103     }104 105 }aho;106 char s[Nmax];107 int main()108 {109     int t;110 //freopen("in.in","r",stdin);111     scanf("%d",&t);112     while(t--)113     {114         int n;115         aho.init();116         scanf("%d",&n);117         while(n--)118         {119             scanf("%s",s);120             aho.insert(s);121         }122         scanf("%s",s);123         aho.build();124         printf("%d\n", aho.match(s)); 125     }126     return 0;127 }