1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string.h> 5 #include <string> 6 #include <queue> 7 using namespace std; 8 const int N=1002; 9 char str[2000005],s1[N][52];10 int ch[50010][26];11 int val[50010],sz,n,root,fail[50010],count1[N];12 int newnode(){13     memset(ch[sz],-1,sizeof(ch[sz]));14     val[sz]=-1;15     return sz++;16 }17 void init(){18     sz=0;19     root=newnode();20 }21 void insert(char* st,int id){22     int len=strlen(st);23     int now=root;24     for(int i=0;i<len;i++){25         int &u=ch[now][st[i]-‘A‘];26         if(u==-1)u=newnode();27         now=u;28     }29     val[now]=id;30     count1[id]=0;31 }32 void getfail(){33     queue<int> q;34     fail[root] = root;35     for(int i=0;i<26;i++){36         int &u=ch[root][i];37         if(u!=-1){38             fail[u]= 0;39             q.push(u);40         }41         else u=root;42     }43     while(!q.empty()){44         int now=q.front();45         q.pop();46         for(int i=0;i<26;i++){47             int u=ch[now][i];48             if(u==-1)ch[now][i]=ch[fail[now]][i];49             else {50                 fail[u]=ch[fail[now]][i];51                 q.push(u);52             }53         }54     }55 }56 void  query(char *s){57     int len=strlen(s);58     int now=root;59     for(int i=0;i<len;i++){60         if(s[i]>‘Z‘||s[i]<‘A‘)now=root;61         else {62             now=ch[now][s[i]-‘A‘];63             int tem=now;64             while(tem!=root){65                 if(val[tem]!=-1)count1[val[tem]]++;66                 tem=fail[tem];67             }68         }69     }70 }71 int main(){72     int i;73     while(scanf("%d",&n)!=EOF){74         init();75         for(i=1;i<=n;i++){76             scanf("%s",s1[i]);77             insert(s1[i],i);78         }79         scanf("%s",str);80         getfail();81         query(str);82         for(i=1;i<=n;i++){83             if(count1[i])84             printf("%s: %d\n",s1[i],count1[i]);85         }86     }87     return 0;88 }