1 #include <cstdio>  2 #include <cstring>  3 #include <queue>  4 #include <algorithm>  5 using namespace std;  6   7 char str[1000010];  8 int t,n;  9 int ans; 10  11 struct node 12 { 13     int v; 14     struct node *next[27],*fail; 15 }*root; 16  17 void insert(char str[]) 18 { 19     struct node *head=root; 20     int k=strlen(str); 21     for(int i=0; i<k; i++) 22     { 23         int x=str[i]-‘a‘; 24         if(head->next[x]==NULL) 25         { 26             struct node *p=(struct node*)malloc(sizeof(struct node)); 27             p->v=0; 28             p->fail=root; 29             for(int j=0; j<26; j++) 30             { 31                 p->next[j]=NULL; 32             } 33             head->next[x]=p; 34         } 35         head=head->next[x]; 36         if(i==k-1) head->v+=1; 37     } 38 } 39  40 node *getFail(node *p,int x) 41 { 42     if(p->next[x]!=NULL) 43     { 44         return p->next[x]; 45     } 46     else 47     { 48         if(p==root) return root; 49         else 50             return getFail(p->fail,x); 51     } 52 } 53  54 void Build_AC() 55 { 56     node *head,*p; 57     queue<node *>q; 58     q.push(root); 59     while(!q.empty()) 60     { 61         head=q.front(); 62         q.pop(); 63         for(int j=0; j<26; j++) 64         { 65             if(head->next[j]!=NULL) 66             { 67                 q.push(head->next[j]); 68                 if(head==root) 69                 { 70                     head->next[j]->fail=root; 71                 } 72                 else 73                 { 74                     bool flag=false; 75                     p=head->fail; 76                     while(p->next[j]==NULL) 77                     { 78                        if(p==root) 79                        { 80                           flag=true; 81                           break; 82                        } 83                        p=p->fail; 84                     } 85                     if(flag) head->next[j]->fail=root; 86                     else 87                     head->next[j]->fail=p->next[j]; 88                 } 89             } 90  91         } 92     } 93 } 94  95 int Find(char str[]) 96 { 97     node *head=root; 98     int k=strlen(str); 99     int cnt=0;100     for(int i=0; i<k; i++)101     {102         int x=str[i]-‘a‘;103         while(head->next[x]==NULL&&head!=root) head=head->fail;104         if(head->next[x]==NULL) head=root;105         else head=head->next[x];106         node *p=head;107         while(p!=root)108         {109             cnt+=p->v;110             p->v=0;111             p=p->fail;112         }113     }114     return cnt;115 }116 117 118 int main()119 {120     scanf("%d",&t);121     while(t--)122     {123         ans=0;124         scanf("%d",&n);125         root=(struct node *)malloc(sizeof(struct node));126         root->v=0;127         root->fail=root;128         for(int i=0; i<26; i++)129         {130             root->next[i]=NULL;131         }132         for(int i=1; i<=n; i++)133         {134             scanf("%s",str);135             insert(str);136         }137         Build_AC();138         scanf("%s",str);139         ans=Find(str);140         printf("%d\n",ans);141     }142     return 0;143 }