AC自动机

所谓AC自动机，其实是kmp算法与字典树的结合,不懂这两个，是无法学会的。

自动机

自动机，是一个五元组，包括了状态的非空有穷集合，符号的有限集合，状态转移函 数， 开始状态，终止状态集合，而在字典树上，增加了两个新的东西，一个标记了终止状态集合，另一个辅助了状态转移函数。 我们利用字典树上 的节点来表示状态，而边则用来表示状态转移函数的一部分。

匹配

当AC自动机建立好了以后，我们就可以在AC自动机上进行匹配了，我们在自动机上一 个一个 节点忘下跑，一直到失配，即到达AC自动机上某个节点后，此节点所代表的字符串，与母串的当前前缀子串相差刚好只为最后一个字母，这 时候，我们跳跃到fail指针即可进行后面的继续匹配。

file指针

fail指针当然跳得越深越好，这时候fail所代表的意义到底是什么呢？很明显，此时 要求与母串有 尽可能长得公共前缀，也就是说与失配发生的时候AC自动机所在节点（所表示的状态）表示的字符串的尽可能长的后缀相同的新节点 ， 这里我们明显可以采取树形dp来得到。

内存开销

我们用fail[u]表示节点u的失配指针，用nex[u][i]表示节点u的指向 字符i的节点， 于是我们发现 了转移式子： fail[nex[u][i]]= nex[fail[u]][i];如果fail[u]有儿子i的话，但如果没有呢？我们又要不断往上面跳跃对吧。 复杂度不是特别高，能忍受，当然这是在u有节点i的情况下。如果没有节点呢？sorry，这个问题有点复杂，一般的AC自动机不关心这种事情。因为那 会增加很多额外的开销，我们不愿意去给他们建立新节点来储存fail指针的。

字典图

有一种AC自动机，他索性把字典树建成了字典图，如果nex指针指向空节点，他 一定会导致失配，他的nex指针就直接指向了应该是fail指针的地方，很漂亮的做法，但是我们失去了很多，比方说，树没有了，AC自动机不能再加入新 的模式串了。这让我们很难受，抉择产生了，要么选择字典树+好几倍的新空间开销，要么选择字典图。

更好的解决方案

笔者对此思考了很久，很久，考虑到我们要么用-1要么用0来表示nex指针指向的 是空节点，也就是说，负数没有被使用到，我们可以这样做，如果一条边在字典树上，我们正常储存，如果他不在字典树，而是在字典图上，那我们存储 他所指向的节点的相反数，一者表示此指针指向空节点，再者表示此指针指向的节点的fail指针，这样的做法集合了上诉两种做法的优点于一身。下面是我的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
struct Aho_Corasick_automation{
    static const int maxn=1e6+5;
    int trans[maxn][26],fail[maxn],end[maxn];
    int root,cnt;

    inline int new_node(){
        //fail指针不需要初始化,因为在bfs的时候他被更新
        for(int i=0;i<26;i++)trans[cnt][i]=0;
        end[cnt]=0;
        return cnt++;
    }

    void ini(){
        cnt=0;
        root=new_node();
    }

    void extend(char*buf){
        int len=(int)strlen(buf+1);
        int u=root;
        for(int i=1;i<=len;i++){
            if(trans[u][buf[i]-'a']==0)
                trans[u][buf[i]-'a']=new_node();
            u=trans[u][buf[i]-'a'];
        }
        end[u]++;
    }

    void get_fail(){
        queue<int>q;
        q.push(root);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(trans[u][i]==0){
                    trans[u][i]=-abs(trans[fail[u]][i]);//采用负数来表示非树边。。
                }
                else{
                    q.push(trans[u][i]);
                    fail[trans[u][i]]=abs(trans[fail[u]][i]);
                    if(u==root)fail[trans[u][i]]=root;
                }
            }
        }
    }

    int query(char*buf){//统计母串里面出现了几种子串
        int len=(int)strlen(buf+1);
        int u=root ,ret=0;
        for(int i=1;i<=len;i++){
            u=abs(trans[u][buf[i]-'a']);
            for(int p=u;p!=root;p=fail[p]){
                if(end[p]==-1)break;
                ret+=end[p];
                end[p]=-1;//为什么要搞-1呢？可以用来剪枝，预防这样的特殊数据-> aaaaaaaaaaa......
            }
        }
        return ret;
    }

    void debug(){
        for(int i=0;i<35;i++)printf(" ");
        for(int j=0;j<26;j++){
            printf("%2c",j+'a');
        }
        puts("");
        for(int i=0;i<cnt;i++){
            printf("id=%3d | fail=%3d | end=%3d | chi=[",i,fail[i],end[i]);
            for(int j=0;j<26;j++){
                printf("%2d",trans[i][j]);
            }
            printf("]\n");
        }
    }
};