AC自动机数组实现

AC自动机的实现原理是KMP + 字典树。学AC自动机之前要先去学KMP 和字典树。

第一步先构建一个字典树。

 1 void Insert(){
 2     int rt = 1, len = strlen(str);
 3     for(int i = 0; i < len; i++){
 4         int id = str[i] - 'a';
 5         if(trie[rt][id] == 0){
 6             cnt[tot] = 0;
 7             fair[tot] = 0;
 8             trie[rt][id] = tot++;
 9         }
10         rt = trie[rt][id];
11     }
12     cnt[rt]++;
13 }

插入字典树

第二步通过BFS来构造fair指针。

 1 void Build_tree(){
 2     queue<int> q;
 3     q.push(1);
 4     int p;
 5     while(!q.empty()){
 6         int tmp = q.front();
 7         q.pop();
 8         for(int i = 0; i < 26; i++){
 9             if(trie[tmp][i] != 0){
10                 if(tmp == 1)
11                     fair[trie[tmp][i]] = 1;
12                 else{
13                     p = fair[tmp];
14                     while(p){
15                         if(trie[p][i]){
16                             fair[trie[tmp][i]] = trie[p][i];
17                             break;
18                         }
19                         else p = fair[p];
20                     }
21                     if(!p)  fair[trie[tmp][i]] = 1;
22                 }
23                 q.push(trie[tmp][i]);
24             }
25         }
26     }
27 }

构造fair指针

第三步进行匹配。

统计有多少个单词的出现过。

 1 int Query(){
 2     int rt = 1, ret = 0, len = strlen(str);
 3     for(int i = 0; i < len; i++){
 4         int id = str[i] - 'a';
 5         while(!trie[rt][id] && rt != 1) rt = fair[rt];
 6         rt = trie[rt][id];
 7         if(rt == 0) rt = 1;
 8         int tmp = rt;
 9         while(tmp != 1){
10             if(cnt[tmp] >= 0){
11                 ret += cnt[tmp];
12                 cnt[tmp] = -1;
13             }
14             else break;
15             tmp = fair[tmp];
16         }
17     }
18     return ret;
19 }

统计单词个数。

AC自动机模板题 HDU-2222 Keywords Search

  1 #include<bits/stdc++.h>
  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<int,int> 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<int> 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
", Query());
100     }
101     return 0;
102 }

HDU-2222

AC自动机 数组实现

AC自动机数组实现