zoj3430Detect the Virus(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 using namespace std;
 11 #define N 53769
 12 #define NN 15010
 13 #define LL long long
 14 #define INF 0xfffffff
 15 const double eps = 1e-8;
 16 const double pi = acos(-1.0);
 17 const double inf = ~0u>>2;
 18 const int child_num = 258;
 19 char s[NN],vir[NN];
 20 int di[NN*8],od[NN],vv[NN];
 21 bool f[N];
 22 class ACAutomation
 23 {
 24     private:
 25     int ch[N][child_num];
 26     int val[N];
 27     int fail[N];
 28     int Q[N];
 29     int id[258];
 30     int sz;
 31    // int dp[2][N][1<<10];
 32     public:
 33     void init()
 34     {
 35         fail[0] = 0;
 36         for(int i = 0 ; i < child_num;  i++)
 37         id[i] = i;
 38     }
 39     void reset()//初始化
 40     {
 41         memset(ch[0],0,sizeof(ch[0]));
 42         memset(val,0,sizeof(val));
 43         sz = 1;
 44     }
 45     void insert(int *a,int key,int k)//建立trie树
 46     {
 47         int p = 0;
 48         for( int i = 0; i < k ; i++)
 49         {
 50             int c = id[a[i]];
 51             if(ch[p][c]==0)
 52             {
 53                 memset(ch[sz],0,sizeof(ch[sz]));
 54                 ch[p][c] = sz++;
 55             }
 56             p = ch[p][c];

 57         }
 58         val[p] += key;
 59     }
 60     void construct()//构建fail指针
 61     {
 62         int head = 0,tail = 0,i;
 63         for(i = 0 ;i < child_num ; i++)
 64         {
 65             if(ch[0][i])
 66             {
 67                 fail[ch[0][i]] = 0;
 68                 Q[tail++] = ch[0][i];
 69             }
 70         }
 71         while(head!=tail)
 72         {
 73             int u = Q[head++];
 74             for(i = 0 ;i < child_num ;i ++)
 75             {
 76                 if(ch[u][i]!=0)
 77                 {
 78                     Q[tail++] = ch[u][i];
 79                     fail[ch[u][i]] = ch[fail[u]][i];
 80                 }
 81                 else
 82                 ch[u][i] = ch[fail[u]][i];
 83             }
 84         }
 85     }
 86     int work(int *s,int k)
 87     {
 88         int p = 0,ans = 0;
 89         memset(f,0,sizeof(f));
 90         for(int i = 0; i < k ; i++)
 91         {
 92             int d = id[s[i]];
 93             p = ch[p][d];
 94             int tmp = p;
 95             while(tmp!=0&&!f[tmp])
 96             {
 97                 ans+=val[tmp];
 98                 f[tmp] = 1;
 99                 tmp = fail[tmp];
100             }
101         }
102         return ans;
103     }
104 }ac;
105 int change(char *a)
106 {
107     int i,k = strlen(a),j;
108     int g = 0,gg,num =0 ;
109     for(i = 0;i < k ; i++)
110     {
111         if(a[i]==‘=‘)
112         {
113             num++;
114             continue;
115         }
116         int x = od[a[i]];gg=0;
117         for(j=5;j>=0;j--)
118         {
119             di[g++]=((x&(1<<j))>0);
120         }
121     }
122     if(num==1)
123     g-=2;
124     else if(num==2)
125     g-=4;
126     gg = 0;
127     int y = 0;
128     for(j = 0 ;j < g ; j++)
129     {
130         y+=di[j]*(1<<(7-j%8));
131         if((j+1)%8==0)
132         {
133             vv[gg++] = y;
134             y = 0;
135         }
136     }
137     return g/8;
138 }
139 int main()
140 {
141     int n,i,m;
142     for(i = ‘A‘ ; i <= ‘Z‘ ; i++)
143     od[i] = i-‘A‘;
144     for(i = ‘a‘ ; i <= ‘z‘ ; i++)
145     od[i] = 26+i-‘a‘;
146     for(i = ‘0‘; i <= ‘9‘ ; i++)
147     od[i] = 52+i-‘0‘;
148     od[‘+‘] = 62,od[‘/‘] = 63;
149     ac.init();
150     while(scanf("%d",&n)!=EOF)
151     {
152         ac.reset();
153         for(i = 1; i <= n; i++)
154         {
155             scanf("%s",vir);
156             int len = change(vir);
157             ac.insert(vv,1,len);
158         }
159         ac.construct();
160         scanf("%d",&m);
161         for(i = 1; i <= m ;i++)
162         {
163             scanf("%s",s);
164             int len = change(s);
165             printf("%d\n",ac.work(vv,len));
166         }
167         puts("");
168     }
169     return 0;
170 }