HDU 3065 病毒侵袭持续中

又是一个AC自动机模板，就是和病毒侵袭的区别就是统计的东西不一样，无脑拍完，就当练习手速吧o(╯□╰)o
  1 #include <cstdio>
  2 #include <sstream>
  3 #include <fstream>
  4 #include <cstring>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <map>
  8 #include <cctype>
  9 #include <ctime>
 10 #include <set>
 11 #include <climits>
 12 #include <vector>
 13 #include <queue>
 14 #include <stack>
 15 #include <cstdlib>
 16 #include <cmath>
 17 #include <string>
 18 #include <list>
 19 
 20 #define INPUT_FILE "in.txt"
 21 #define OUTPUT_FILE "out.txt"
 22 
 23 using namespace std;
 24 
 25 typedef long long LL;
 26 const int INF = INT_MAX / 2;
 27 
 28 void setfile() {
 29     freopen(INPUT_FILE,"r",stdin);
 30     freopen(OUTPUT_FILE,"w",stdout);
 31 }
 32 
 33 const int maxn = 1000 + 5;
 34 const int maxlen = 55;
 35 const int maxtlen = 2000000 + 5;
 36 const int maxnode = maxn * maxlen;
 37 const int sigma_size = 128;
 38 
 39 int cnt[maxn];
 40 char buf[maxn][maxlen];
 41 char t[maxtlen];
 42 
 43 struct AC_automation {
 44     int ch[maxnode][sigma_size],val[maxnode];
 45     int sz,fail[maxnode];
 46     
 47     void init() {
 48         sz = 1; memset(ch[0],0,sizeof(ch[0]));
 49     }
 50 
 51     inline int idx(char c) {
 52         return c;
 53     }
 54 
 55     void insert(char *str,int id) {
 56         int len = strlen(str),u = 0;
 57         for(int i = 0;i < len;i++) {
 58             int c = idx(str[i]);
 59             if(ch[u][c] == 0) {
 60                 memset(ch[sz],0,sizeof(ch[sz]));
 61                 fail[sz] = val[sz] = 0;
 62                 ch[u][c] = sz++;
 63             }
 64             u = ch[u][c];
 65         }
 66         val[u] = id;
 67     }
 68 
 69     void construct() {
 70         queue<int> q;
 71         int u = 0;
 72         for(int i = 0;i < sigma_size;i++) {
 73             if(ch[u][i]) {
 74                 q.push(ch[u][i]);
 75                 fail[ch[u][i]] = 0;
 76             }
 77         }
 78 
 79         while(!q.empty()) {
 80             u = q.front(); q.pop();
 81             for(int i = 0;i < sigma_size;i++) {
 82                 int &v = ch[u][i];
 83                 if(v) {
 84                     fail[v] = ch[fail[u]][i];
 85                     q.push(v);
 86                 } else {
 87                     v = ch[fail[u]][i];
 88                 }
 89             }
 90         }
 91     }
 92 
 93     void query(char *str) {
 94         memset(cnt,0,sizeof(cnt));
 95         int len = strlen(str),u = 0;
 96         for(int i = 0;i < len;i++) {
 97             int c = idx(str[i]);
 98             u = ch[u][c];
 99             int v = u;
100             while(v) {
101                 if(val[v]) cnt[val[v]]++;
102                 v = fail[v];
103             }
104         }
105     }
106 };
107 
108 AC_automation ac;
109 
110 int main() {
111     int n;
112     while(~scanf("%d",&n)) {
113         getchar();
114         ac.init();
115         for(int i = 1;i <= n;i++) {
116             gets(buf[i]);
117             ac.insert(buf[i],i);
118         }
119         ac.construct();
120         gets(t);
121         ac.query(t);
122         for(int i = 1;i <= n;i++) if(cnt[i]) {
123             printf("%s: %d
",buf[i],cnt[i]);
124         }
125     }
126     return 0;
127 }