AC自动机

数组版

 1 struct Tire{
 2     int next[maxn][27],fail[maxn],dis[maxn];
 3     int root,L;
 4     queue<int >q;
 5 
 6     int newnode(){
 7         dis[L] = 0;
 8         for(int i = 0; i < 26; i++)
 9             next[L][i] = -1;
10         L++;
11         return L-1;
12     }
13     void ini(){
14         while(q.size()) q.pop();
15         L = 0,root = newnode();
16     }
17     int cha(char x){
18         return x-'a';
19     }
20     void inser(char buf[]){
21         int len = strlen(buf);
22         int now = root;
23         for(int i = 0; i < len; i++){
24             int ta = cha(buf[i]);
25             if(next[now][ta] == -1)
26                 next[now][ta] = newnode();
27             now = next[now][ta];
28         }
29         dis[now] ++;
30     }
31     void build(){
32         fail[root] = root;
33         for(int i = 0; i < 26; i++)
34             if(next[root][i] == -1)
35                 next[root][i] = root;
36             else{
37                 fail[next[root][i]] = root;
38                 q.push(next[root][i]);
39             }
40         while(!q.empty()){
41             int now = q.front();
42             q.pop();
43             for(int i = 0; i < 26; i++){
44                 if(next[now][i] == -1)
45                     next[now][i] = next[fail[now]][i];
46                 else{
47                     fail[next[now][i]] = next[fail[now]][i];
48                     q.push(next[now][i]);
49                 }
50             }
51         }
52     }
53     int solve(char* str){
54         int cur = root;
55         int len = strlen(str);
56         int index;
57         int cnt = 0;
58         for(int i = 0; i < len; i++){
59             index = cha(str[i]);
60             cur = next[cur][index];
61             int tp = cur;
62             while(tp != root && dis[tp] != -1){
63                 if(dis[tp] > 0){
64                     cnt += dis[tp];
65                     dis[tp] = -1;
66                 }
67                 tp = fail[tp];
68             }
69         }
70         return cnt;
71     }
72 };

指针版

 1 struct node{
 2     node *fail;//记录匹配失败时要跳到哪个节点
 3     node *next[26];
 4     int v;//是否为最后一个节点
 5     node(){
 6         v = 0;
 7         fail = NULL;
 8         memset(next,NULL,sizeof(next));
 9     }
10 }*q[10000*50+5];//队列
11 
12 char s1[51];//匹配串
13 char s2[1000005];//母串
14 int head,tail;//队头队尾，注意初始化
15 void build(char *s,node *root){//建一棵字典树
16     node *p = root;
17     int i=0,index;
18     while(s[i]){
19         index = s[i] - 'a';
20        if(p->next[index] == NULL) p->next[index] = new node();
21         p = p->next[index];
22         i++;
23     }
24     p->v ++;//最后一个节点++，表示出现次数加1
25 }
26 void buildac(node *root){//在字典树上做类似kmp的操作,表示匹配失败时应该跳到什么位置
27 root->fail = NULL;
28 head = tail = 0;
29     q[head++] = root;
30     while(head!=tail){
31         node *p = q[tail++];
32         node *temp = NULL;
33         for(int i=0;i<26;i++){
34             if(p->next[i] != NULL){
35                 q[head++] = p->next[i];
36                 if(p == root) p->next[i]->fail = root;
37                 else{
38                     temp = p->fail;
39                     while(temp!=NULL){
40                         if(temp->next[i]!=NULL){
41                             p->next[i]->fail = temp->next[i];
42                             break;
43                         }
44                         temp = temp->fail;
45                     }
46                     if(temp == NULL) p->next[i]->fail = root;
47                 }
48             }
49         }
50     }
51 }