zoj3228Searching the String（ac自动机)

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 #include<string>
 11 #include<map>
 12 using namespace std;
 13 #define N 600110
 14 #define LL long long
 15 #define INF 0xfffffff
 16 const double eps = 1e-8;
 17 const double pi = acos(-1.0);
 18 const double inf = ~0u>>2;
 19 const int child_num = 26;
 20 char vir[10];
 21 char s[N/6];
 22 int o[N/6],len[N/6],ans[N/6][2],po[N/6];
 23 int cc[N/6];
 24 map<string,int>f;
 25 vector<int>ed[N/6];
 26 class AC
 27 {
 28     private:
 29     int ch[N][child_num];
 30     int fail[N];
 31     int Q[N];
 32     int val[N];
 33     int sz;
 34     int id[128];
 35     public:
 36     void init()
 37     {
 38         fail[0] = 0;
 39         for(int i = 0 ;i < child_num ; i++)
 40         id[i+‘a‘] = i;
 41     }
 42     void reset()
 43     {
 44         memset(ch[0],0,sizeof(ch[0]));
 45         memset(val,0,sizeof(val));
 46         sz = 1;
 47     }
 48     void insert(char *a,int key)
 49     {
 50         int p = 0;
 51         for(; *a ; a++)
 52         {
 53             int d= id[*a];
 54             if(ch[p][d]==0)
 55             {
 56                 memset(ch[sz],0,sizeof(ch[sz]));
 57                 ch[p][d] = sz++;
 58             }
 59             p = ch[p][d];
 60         }
 61         val[p] = key;
 62     }
 63     void construct()
 64     {
 65         int i,head=0,tail = 0;
 66         for(i = 0; i  < child_num ;i++)
 67         {
 68             if(ch[0][i])
 69             {
 70                 fail[ch[0][i]] = 0;
 71                 Q[tail++] = ch[0][i];
 72             }
 73         }
 74         while(head!=tail)
 75         {
 76             int u = Q[head++];
 77             for(i = 0; i < child_num ; i++)
 78             {
 79                 if(ch[u][i])
 80                 {
 81                     fail[ch[u][i]] = ch[fail[u]][i];
 82                     Q[tail++] = ch[u][i];
 83                 }
 84                 else ch[u][i] = ch[fail[u]][i];
 85             }
 86         }
 87     }
 88     void work(int m,int kk,int g)
 89     {
 90         memset(ans,0,sizeof(ans));
 91         memset(po,-1,sizeof(po));
 92         int p = 0,i,k = strlen(s);
 93         for(i = 0 ; i < k ; i++)
 94         {
 95             int d = id[s[i]];
 96             p = ch[p][d];
 97             int tmp = p;
 98             while(tmp)
 99             {
100                 int v = val[tmp];
101                 ans[v][0]++;
102                 if(po[v]+len[v]<=i)
103                 {
104                     po[v] = i;
105                     ans[v][1]++;
106                 }
107                 tmp = fail[tmp];
108             }
109         }
110         for(i = 1; i <= g ; i++)
111         {
112             for(int j = 0; j < ed[i].size() ; j++)
113             {
114                 int v = ed[i][j];
115                 if(o[v]) cc[v] = ans[i][1];
116                 else cc[v] = ans[i][0];
117             }
118         }
119         printf("Case %d\n",kk);
120         for(i = 1 ; i <= m ;i++)
121         printf("%d\n",cc[i]);
122         puts("");
123     }
124 }ac;
125 int main()
126 {
127     int i,m,kk=0;
128     ac.init();
129     while(scanf("%s",s)!=EOF)
130     {
131         ac.reset();
132         f.clear();
133         scanf("%d",&m);
134         int g = 0;
135         for(i = 1 ; i <= m; i++)
136         ed[i].clear();
137         for(i = 1;i <= m ;i++)
138         {
139             scanf("%d%s",&o[i],vir);
140             if(!f[vir])
141             {
142                 f[vir] = (++g);
143                 ac.insert(vir,g);
144                 len[g] = strlen(vir);
145             }
146             ed[f[vir]].push_back(i);
147         }
148         ac.construct();
149         kk++;
150         ac.work(m,kk,g);
151     }
152     return 0;
153 }