1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月11日 星期四 15时18分26秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<queue> 25 #define LL long long 26 #define maxn 1010*50 27 using namespace std; 28 int hs[1010]; 29 struct Trie 30 { 31     int next[maxn][26],fail[maxn],end[maxn]; 32     int root, L; 33     int newnode() 34     { 35         for(int i = 0 ;i < 26;i ++) 36             next[L][i] = -1; 37         end[L++] = 0 ; 38         return L-1; 39     } 40     void init() 41     { 42          L = 0 ;  43         root = newnode(); 44     } 45     void insert(char buf[],int K) 46     { 47         int len = strlen(buf); 48         int now = root; 49         for(int i = 0 ;i < len ;i ++) 50         { 51             int tt = buf[i] - ‘A‘; 52             if(next[now][tt] ==  -1) 53             { 54                 next[now][tt] = newnode(); 55             } 56             now = next[now][tt]; 57         } 58         end[now] = K; 59     } 60     void build() 61     { 62         queue<int> Q; 63         fail[root] = root;  64         for(int i = 0;i < 26;i ++) 65         { 66             if(next[root][i] == -1) 67             { 68                 next[root][i] = root;  //指向root 是没有问题的，我们主要是通过end 数组对个数进行计数的。     69             }else{ 70                 fail[next[root][i]] = root; 71                 Q.push(next[root][i]); 72             } 73         } 74         while(!Q.empty()) 75         { 76             int now = Q.front(); 77             Q.pop(); 78             for(int i = 0 ;i < 26;i ++) 79             { 80                 if(next[now][i] == -1) 81                     next[now][i] =  next[fail[now]][i];  82                 else{ 83                     fail[next[now][i]] = next[fail[now]][i]; 84                     Q.push(next[now][i]); 85                 } 86             } 87         } 88     } 89     void query(char buf[]) 90     { 91         int now = root ;  92         int len = strlen(buf); 93         for(int  i = 0 ;i <= len;i ++) 94         { 95             if(!(buf[i] <= ‘Z‘ && buf[i] >= ‘A‘)) 96             { 97                 now = root ;  98                 continue; 99             }100             now = next[now][buf[i] - ‘A‘];101             int temp = now ; 102             while(temp != root)103             {104                 if(end[temp])105                 {106                     hs[end[temp]] ++ ; 107                 }108                 temp = fail[temp];109             }110         }111     }112 };113 char str[1005][100];114 char buf[2100010];115 Trie ac;116 int main(){117     int n;118     while(scanf("%d",&n) != EOF)119     {120         ac.init();121         for(int i = 1 ;i <= n;i ++)122         {123             scanf("%s",str[i]);124             ac.insert(str[i],i);125         }126         ac.build();127         memset(hs,0,sizeof(hs));128         scanf("%s",buf);129         ac.query(buf);130         for(int i = 1;i <= n;i ++)131         {132             if(hs[i])133             {134                 printf("%s: %d\n",str[i],hs[i]);135             }136         }137     }138     return 0;139 }