AC自动机 模板题 

1 #include
      
         2 using namespace std;  3 #define LL long long  4 #define ULL unsigned LL  5 #define fi first  6 #define se second  7 #define lson l,m,rt<<1  8 #define rson m+1,r,rt<<1|1  9 #define max3(a,b,c) max(a,max(b,c)) 10 #define min3(a,b,c) min(a,min(b,c)) 11 const int INF = 0x3f3f3f3f; 12 const LL mod = 1e9+7; 13 typedef pair
       
         pll; 14 const int N = 1e5+10, M = 1e3; 15 char str[N*10]; 16 int trie[N*10][26]; 17 int fair[N*26]; 18 int cnt[N*26]; 19 int tot = 2; 20 void Insert(){ 21     int rt = 1, len = strlen(str); 22     for(int i = 0; i < len; i++){ 23         int id = str[i] - 'a'; 24         if(trie[rt][id] == 0){ 25             cnt[tot] = 0; 26             fair[tot] = 0; 27             trie[rt][id] = tot++; 28         } 29         rt = trie[rt][id]; 30     } 31     cnt[rt]++; 32 } 33 void Build_tree(){ 34     queue
        
          q; 35     q.push(1); 36     int p; 37     while(!q.empty()){ 38         int tmp = q.front(); 39         q.pop(); 40         for(int i = 0; i < 26; i++){ 41             if(trie[tmp][i] != 0){ 42                 if(tmp == 1) 43                     fair[trie[tmp][i]] = 1; 44                 else{ 45                     p = fair[tmp]; 46                     while(p){ 47                         if(trie[p][i]){ 48                             fair[trie[tmp][i]] = trie[p][i]; 49                             break; 50                         } 51                         else p = fair[p]; 52                     } 53                     if(!p)  fair[trie[tmp][i]] = 1; 54                 } 55                 q.push(trie[tmp][i]); 56             } 57         } 58     } 59 } 60 int Query(){ 61     int rt = 1, ret = 0, len = strlen(str); 62     for(int i = 0; i < len; i++){ 63         int id = str[i] - 'a'; 64         while(!trie[rt][id] && rt != 1) rt = fair[rt]; 65         rt = trie[rt][id]; 66         if(rt == 0) rt = 1; 67         int tmp = rt; 68         while(tmp != 1){ 69             if(cnt[tmp] >= 0){ 70                 ret += cnt[tmp]; 71                 cnt[tmp] = -1; 72             } 73             else break; 74             tmp = fair[tmp]; 75         } 76     } 77     return ret; 78 } 79 void init(){ 80     for(int i = 1; i < tot; i++){ 81         for(int j = 0; j < 26; j++) 82             trie[i][j] = 0; 83     } 84     tot = 2;  85 } 86 int main(){ 87     int T; 88     scanf("%d", &T); 89     while(T--){ 90         init(); 91         int n; 92         scanf("%d", &n); 93         while(n--){ 94             scanf("%s", str); 95             Insert(); 96         } 97         Build_tree(); 98         scanf("%s", str); 99         printf("%d\n", Query());100     }101     return 0;102 }
        
       
      

 

 

2进制分组AC自动机

假如给你21个串： 分为 16+4+1，再添加一个串的时候，即21+1， 22 = 16+4+1+1 = 16 + 4 + 2。 这样每次加串之后只会有logn个操作，查询也变成logn操作， 对于同一个串建立fair指针的次数就少了。

1 #include
      
        2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<110 #define rson m+1,r,rt<<1|111 #define max3(a,b,c) max(a,max(b,c))12 #define min3(a,b,c) min(a,min(b,c))13 typedef pair
       
         pll;14 const int INF = 0x3f3f3f3f;15 const LL mod =  (int)1e9+7;16 const int N = 3e5 + 100;17 struct Node{18     static const int m = 26;static const int KN = N;19     int next[KN][m], fair[KN], tot = 0, mark[KN], mark1[KN], root[20], cnt = 0, si[20];20     void Build(int x){21         queue
        
          q;22         q.push(x);23         int pos, p, v;24         while(!q.empty()){25             pos = q.front(), q.pop();26             for(int i = 0; i < m; i++){27                 if(!next[pos][i]) continue;28                 p = fair[pos]; v = next[pos][i];29                 while(p && !next[p][i]) p = fair[p];30                 if(p) fair[v] = next[p][i];31                 else fair[v] = x;32                 q.push(v);33                 mark1[v] = mark1[fair[v]] + mark[v];34             }35         }36     }37     void Add(char s[], char ch){38         root[++cnt] = ++tot; si[cnt] = 1;39         int pos = root[cnt];40         for(int i = 0; s[i]; i++){41             if(!next[pos][s[i]-ch]) next[pos][s[i]-ch] = ++tot;42             pos = next[pos][s[i]-ch];43         }44         mark[pos]++;45         while(si[cnt] == si[cnt-1]){46             Unit(root[cnt-1], root[cnt]);47             si[--cnt] *= 2;48         }49         Build(root[cnt]);50     }51     int Query(char s[], char ch){52         int pos, ret = 0;53         for(int id = 1; id <= cnt; id++){54             pos = root[id];55             for(int i = 0; s[i]; i++){56                 while(pos && !next[pos][s[i]-ch]) pos = fair[pos];57                 if(pos) pos = next[pos][s[i]-ch];58                 else pos = root[id];59                 ret += mark1[pos];60             }61         }62         return ret;63     }64     void Unit(int u, int v){65         mark[u] += mark[v];66         for(int i = 0; i < m; i++){67             if(!next[u][i] || !next[v][i]) next[u][i] += next[v][i];68             else Unit(next[u][i], next[v][i]);69         }70     }71 }ac[2];72 char str[N];73 int main(){74     int n, k;75     scanf("%d", &n);76     while(n--){77         scanf("%d%s", &k, str);78         if(k <= 2) ac[k-1].Add(str, 'a');79         else {80             printf("%d\n", ac[0].Query(str, 'a')-ac[1].Query(str, 'a'));81             fflush(stdout);82         }83     }84     return 0;85 }86 87 AC自动机