ZOJ - 3228 Searching the String

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 6e5+10;
 5 const int N = 30;
 6 int a[maxn],b[maxn][2],last[maxn];
 7 
 8 struct tire{
 9     int nxt[maxn][N],fail[maxn],c[maxn],end[maxn],tot,root;
10     int newNode(){
11         for(int i=0;i<26;i++) nxt[tot][i] = -1;
12         c[tot++]=0;
13         return tot-1;
14     }
15     void Init(){
16         tot = 0;
17         root = newNode();
18     }
19     void Insert(char *buf,int id){
20         int len = strlen(buf),i,u = root;
21         for(i=0;i<len;i++){
22             int x = buf[i]-'a';
23             if(nxt[u][x]==-1) nxt[u][x] = newNode();
24             c[nxt[u][x]]=c[u]+1;
25             u = nxt[u][x];
26         }
27         end[id] = u;
28     }
29     void build(){
30         queue <int> q;
31         fail[root] = root;
32         for(int i=0;i<26;i++){
33             if(nxt[root][i]==-1) nxt[root][i] = root;
34             else{
35                 fail[nxt[root][i]] = root;
36                 q.push(nxt[root][i]);
37             }
38         }
39         while(!q.empty()){
40             int now = q.front();
41             q.pop();
42             for(int i=0;i<26;i++){
43                 if(nxt[now][i]==-1) nxt[now][i] = nxt[fail[now]][i];
44                 else{
45                     fail[nxt[now][i]] = nxt[fail[now]][i];
46                     q.push(nxt[now][i]);
47                 }
48             }
49         }
50     }
51     void query(char *buf){
52         int len = strlen(buf),now = root;
53         for(int i=0;i<len;i++){
54             int x = buf[i]-'a';
55             now = nxt[now][x];
56             int tmp = now;
57             while(tmp!=root){
58                 b[tmp][0]++;
59                 if(i-last[tmp]>=c[tmp]){
60                     b[tmp][1]++;
61                     last[tmp]=i;
62                 }
63                 tmp=fail[tmp];
64             }
65         }
66     }
67 }ac;
68 
69 char s1[10];
70 char s[100100];
71 
72 int main()
73 {
74     int t=0,n;
75     while(scanf("%s",s)!=EOF){
76         t++;
77         scanf("%d",&n);
78         ac.Init();
79         for(int i=0;i<n;i++){
80             scanf("%d",&a[i]);
81             scanf("%s",s1);
82             ac.Insert(s1,i);
83         }
84         ac.build();
85         memset(last,-1,sizeof(last));
86         memset(b,0,sizeof(b));
87         ac.query(s);
88         printf("Case %d\n",t);
89         for(int i=0;i<n;i++){
90             printf("%d\n",b[ac.end[i]][a[i]]);
91         }
92         printf("\n");
93     }
94     return 0;
95 }