1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月11日 星期四 15时18分128秒  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 100010 27 using namespace std; 28 vector<int> ans; 29 struct Trie 30 { 31     int next[maxn][128],fail[maxn],end[maxn]; 32     int root, L; 33     int newnode() 34     { 35         for(int i = 30 ;i < 127;i ++) 36             next[L][i] = -1; 37         end[L++] = 0 ; 38         return L-1; 39     } 40     int init() 41     { 42         int L = 0 ;  43         root = newnode(); 44     } 45     int 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             if(next[now][buf[i]] ==  -1) 52             { 53                 next[now][buf[i]] = newnode(); 54             } 55             now = next[now][buf[i]]; 56         } 57         end[now] = K; 58     } 59     void build() 60     { 61         queue<int> Q;  62         //这里为何要用优先队列来解决这个问题，主要原因是fail指针是按层数来的。 63         fail[root] = root;  64         for(int i = 30;i < 127;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 = 30 ;i < 127;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 len = strlen(buf); 92         int now = root ;  93         for(int i = 0 ;i < len;i ++) 94         { 95             now = next[now][buf[i]]; 96             int temp = now ;  97             while(temp != root) 98             { 99                 if(end[temp])100                     ans.push_back(end[temp]);    101                 temp = fail[temp];102             }103         }104     }105 };106 char buf[10010];107 Trie ac;108 int main(){109     int n;110     while(scanf("%d",&n) != EOF)111     {112         ac.init();113         getchar();114         for(int i = 1 ;i <= n;i ++)115         {116             scanf("%[^\n]",buf);117             getchar();118             ac.insert(buf,i);119         }120         ac.build();121         int m;122         scanf("%d",&m);123             getchar();124         int sum = 0 ; 125         for(int i = 1;i <= m;i ++)126         {127             scanf("%s",buf);128             getchar();129             //printf("***");130             ans.clear();131             ac.query(buf);132             if(ans.size() != 0 )133             {134                 sum ++;135             }else{136               continue;137             }138             sort(ans.begin(),ans.end());139             printf("web %d: ",i);140             for(int j = 0 ;j < ans.size();j ++)141                 printf(j == 0 ?"%d":" %d",ans[j]);142             printf("\n");143         }144         printf("total: %d\n",sum);145     }146     return 0;147 }