1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月11日 星期四 15时18分4秒  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 100105*7 27 using namespace std; 28 int hs[100105]; 29 struct Trie 30 { 31     int next[maxn][26],fail[maxn],end[maxn],ansend0[maxn],ansend1[maxn],first[maxn]; 32     vector <int> exend0[maxn]; 33     vector <int> exend1[maxn]; 34     int root, L; 35     int newnode() 36     { 37         memset(next[L],-1,sizeof(next[L])); 38         exend0[L].clear(); 39         exend1[L].clear(); 40         ansend0[L] =0 ; 41         ansend1[L] = 0 ; 42         end[L++] = 0 ; 43         return L-1; 44     } 45     void init() 46     { 47         L = 0 ;  48         root = newnode(); 49     } 50     void insert(char buf[] ,int k ,int status) 51     { 52         int now = root; 53         int len = strlen(buf); 54         for(int i = 0 ;i < len ;i ++) 55         { 56             if(next[now][buf[i] - ‘a‘] ==  -1) 57             { 58                 next[now][buf[i] - ‘a‘] = newnode(); 59             } 60             now = next[now][buf[i]- ‘a‘]; 61         } 62         end[now] = len; 63         if(status == 0) 64         { 65           exend0[now].push_back(k); 66         }else{ 67           exend1[now].push_back(k); 68         } 69     } 70     void build() 71     { 72         queue<int> Q; 73         fail[root] = root;  74         for(int i = 0;i < 26;i ++) 75         { 76             if(next[root][i] == -1) 77             { 78                 next[root][i] = root;  //指向root 是没有问题的，我们主要是通过end 数组对个数进行计数的。     79             }else{ 80                 fail[next[root][i]] = root; 81                 Q.push(next[root][i]); 82             } 83         } 84         while(!Q.empty()) 85         { 86             int now = Q.front(); 87             Q.pop(); 88             for(int i = 0 ;i < 26;i ++) 89             { 90                 if(next[now][i] == -1) 91                 { 92                     next[now][i] =  next[fail[now]][i];  93                 } 94                 else{ 95                     fail[next[now][i]] = next[fail[now]][i]; 96                     Q.push(next[now][i]); 97                 } 98             } 99         }100     }101     void query(char buf[])102     {103         memset(first,-1,sizeof(first));104         memset(hs,0,sizeof(hs));105         int len = strlen(buf);106         int now = root;107         for(int i = 0 ;i < len;i ++)108         {109             now = next[now][buf[i] - ‘a‘];110             int temp = now ; 111             while(temp != root)112             {113                if(end[temp])114                {115                    if(first[temp] <= i - end[temp])116                    {117                       ansend1[temp] ++ ;118                       first[temp] = i ; 119                    }120                    ansend0[temp] ++ ; 121                }122                temp = fail[temp];123             }124 125         }126         for(int i = 0 ;i < L ;i ++)127         {128             if(end[i])129             {130               int t = exend0[i].size();131               for(int j = 0 ;j < t ;j ++)132               {133                   hs[exend0[i][j]] = ansend0[i];134               }135               t = exend1[i].size();136               for(int j = 0 ;j < t ;j ++)137               {138                   hs[exend1[i][j]] = ansend1[i];139               }140             141             }142         }143     }144 };145 char buf[101005];146 char temp[10];147 Trie ac;148 int main(){149     int n;150     int ca= 0 ;151     //freopen("in","r",stdin);152     while(scanf("%s",buf) != EOF)153     {154         ca ++ ;155         scanf("%d",&n);156         ac.init();157         int status;158         for(int i =1 ;i <= n;i ++)159         {160             scanf("%d %s",&status,temp);161             ac.insert(temp,i,status);162         }163         ac.build();164         ac.query(buf);165         printf("Case %d\n",ca);166         for(int i = 1;i <= n;i ++)167             printf("%d\n",hs[i]);168         printf("\n");169     }170     return 0;171 }