AC自动机（模板）

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <queue>
  7 
  8 using namespace std;
  9 
 10 int n, ans[500000 + 5];
 11 char str[55][500000 + 5];
 12 
 13 struct AcAutomaton{
 14   static const int N = 500000 + 10;
 15   static const int C = 26;
 16 
 17   int size;
 18   int ch[N][C], fail[N], num[N], end[N];
 19 
 20   AcAutomaton(){
 21     size = 1;
 22   }
 23 
 24   int idx(char c){
 25     return c - 'a';
 26   }
 27   
 28   void insert(char *buf, int k){
 29     int cur = 0, len = strlen(buf);
 30 
 31     for(int i = 0; i < len; ++ i){
 32       int x = idx(buf[i]);
 33 
 34       if(!ch[cur][x])
 35         ch[cur][x] = size ++;
 36       cur = ch[cur][x];
 37     }
 38 
 39     end[cur] ++; num[cur] = k;
 40   }
 41 
 42   void build(){
 43     queue <int> q;
 44     fail[0] = 0;
 45 
 46     for(int i = 0; i < C; ++ i){
 47       if(!ch[0][i]) ch[0][i] = 0;
 48       else{
 49         fail[ch[0][i]] = 0;
 50         q.push(ch[0][i]);
 51       }
 52     }
 53 
 54     while(!q.empty()){
 55       int x = q.front(); q.pop();
 56 
 57       for(int i = 0; i < 26; ++ i){
 58         if(!ch[x][i]) ch[x][i] = ch[fail[x]][i];
 59         else{
 60           fail[ch[x][i]] = ch[fail[x]][i];
 61           q.push(ch[x][i]);
 62         }
 63       }
 64     }
 65   }
 66 
 67   void find(char* buf){
 68     int cur = 0, len = strlen(buf);
 69 
 70     for(int i = 0; i < len; ++ i){
 71       int x = idx(buf[i]);
 72       
 73       cur = ch[cur][x];
 74 
 75       int tmp = cur;
 76       while(tmp){
 77         if(end[tmp])
 78           ans[num[tmp]] += end[tmp];
 79         tmp = fail[tmp];
 80       }
 81     }
 82   }
 83 }ac;
 84 
 85 int main(){
 86 #ifndef ONLINE_JUDGE
 87   freopen("ACautomata.in", "r", stdin);
 88   freopen("ACautomata.out", "w", stdout);
 89 #endif
 90 
 91   scanf("%d", &n);
 92   for(int i = 1; i <= n; ++ i){
 93     scanf("%s", str[i]);
 94     ac.insert(str[i], i);
 95   }
 96   ac.build();
 97   scanf("%s", str[n+1]);
 98   ac.find(str[n+1]);
 99 
100   for(int i = 1; i <= n; ++ i){
101     int tp = strlen(str[i]);
102     for(int j = 0; j < tp; ++ j)
103       printf("%c", str[i][j]);
104     printf(" %d
", ans[i]);
105   }
106   
107 #ifndef ONLINE_JUDGE
108   fclose(stdin); fclose(stdout);
109 #endif
110 
111   return 0;
112 }
AcAutomaton