<---- 我写了这么久，就点个赞吧

$1.$ $AC$ 自动机简介

$AC$ 自动机，不是会自动 $AC$ 的机器，而是由 $Alfred.V.Aho$ 和 $Margaret.J.Corasick$ 发明的 $Aho-Corasick$ 自动机，它能解决多模式串的匹配问题，相当于多模式串的 $KMP$ 。

$2.$ $AC$ 自动机的基本概念

$AC$ 自动机 $= Trie + KMP$
所以 $AC$ 自动机本质是 $Trie$ 树，但加了 $KMP$ 的失配边，使得 $AC$ 自动机的效率和 $KMP$ 几乎一样快。

$3.$ $AC$ 自动机的存储方法

上文已经提到，直接用 $Trie$ 树的存储方式，还要再加一个 $KMP$ 的失配边数组
$Trie$ 树一般要开字符串总个数 $\times$ 字符串最大长度， $AC$ 自动机也是如此。

$4.$ 建立 $AC$ 自动机

思路1

读入所有的字符串，把他们全部扔进 $Trie$ 树中，这里重点讲一下怎么建失配边。
首先拿出 $KMP$ 求 $fail$ 指针的代码（也可以把失配指针取成 $next$ ）

void get_fail () {
    for (int i = 2,j = 0;i <= m;i++) {
        //j = fail[i - 1];  //这里其实是有这一句的，但是j是循环变量，会直接传递，可以省略
        //，但是在AC自动机不能省略，因为它是广搜，不能传递这种信息
        while (j && p[i] != p[j + 1]) j = fail[j];
        if (p[i] == p[j + 1]) j++;
        fail[i] = j;
    }
}

我们对应过来就是某一个字符串的第 $i$ 个字符，就是 $AC$ 自动机中第 $i$ 层！！！（ $Trie$ 中字符串的第几个字母就在第几层）
我们不难发现，每次 $KMP$ 中算 $fail$ 指针，都是用前一个字母的 $fail$ 值计算出来的，对应到 $AC$ 自动机上就是每层的 $fail$ 值，都是由上一层节点的 $fail$ 值算出来的。所以要一层一层的搜，我们很容易想到 $BFS$ 。
因为算 $fail$ 指针是从第 $2$ 层开始算的，所以我们就把所有第 $1$ 层的所有点，扔到队列里，这样扩展出来的所有点就是第 $2$ 层及以下更低层。
我们这里解释一下如果 $fail[i]=j$ ，假设从根节点到 $j$ 的字符串的长度是 $w$ ，则从根节点到 $j$ 的字符串和从 $i$ 往上走的第 $w$ 个父亲到 $i$ 的字符串相等
可以对应这图看一下，虚线是失配边。

话不多说，上代码！

代码1

const int N = 10010,S = 55,M = 1000010;  //N是最大的字符串个数，S是字符串的最大长度，
//M是要匹配字符串的最大长度
int tr[N * S][26],cnt[N * S],idx;  //这些都是Trie树的必备数组
int fail[N * S],q[N * S];   // fail数组和用来求fail数组的手写队列
char str[M];  //由于数据大于100000所以用scanf保险，防止超时
void insert (char s[N]) {  //Trie树的基本插入操作
    int p = 0;
    for (int i = 0;s[i];i++) {
        int t = s[i] - 'a';  //第t个儿子
        if (!tr[p][t]) tr[p][t] = ++idx;  //没有这个儿子就建立它，注意要++idx，防止和根节点的0重复
        p = tr[p][t];
    }
    cnt[p]++;  //最后一个点的单词数量加1
}
void get_fail () {  //建立失配指针
    for (int i = 0;i < 26;i++) {  //遍历所有根节点的儿子，即深度为1的节点
        if (tr[0][i]) q[++tt] = tr[0][i];  //如果根节点有i号儿子就加到队列中
    }
    while (hh <= tt) {  //BFS
        int t = q[hh++];  //取出头节点
        for (int i = 0;i < 26;i++) {  //遍历下一层
            if (p) {
                int j = fail[t];   //对应着KMP中的j = ne[i - 1]
                while (j && !tr[j][i]) j = fail[j];  //如果没有第i个儿子，就是字母不匹配，
                //就跳转失陪边，对应着while (j && p[i] != p[j + 1]) j = fail[j];
                if (tr[j][i]) j = tr[j][i];  // 如果能到下一个字符就到下一个字符，
                // 对应着if (p[i] == p[j + 1]) j++;
                fail[p] = j;  //赋值
                q[++tt] = p;  //入队，继续搜
            }
        }
    }
}

思路2

现在有一种比较好些的 $AC$ 自动机叫 $Trie$ 图，它原本是 $Trie$ 树，但加了一些边后就失去了 $DAG$ 性质，就像一个图一样。这里就直接上代码。

代码2

void get_fail () {
    int hh = 0,tt = -1;
    for (int i = 0;i < 26;i++) {
        if (tr[0][i]) q[++tt] = tr[0][i];
    }
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = 0;i < 26;i++) {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[fail[t]][i];  //要注意，这里就是Trie树变化的部分，可以当成并查集
            //中的路径压缩来理解
            else {
                fail[p] = tr[fail[t]][i];  //这里就是直接指向父亲节点的fail指针的第i个儿子。
                q[++tt] = p;
            }
        }
    }
}

$5.$ 长文本串匹配

思路1

我们先来讲一下直接把 $KMP$ 思路对应过来的方法。
也是一样，直接把 $KMP$ 的代码对应过来。

代码1

void query (char s[M]) {
    for (int i = 0,j = 0;s[i];i++) {  //这里是循环，KMP中的j就可以直接写在循环变量里了
        int t = s[i] - 'a';  //去第t个儿子
        while (j && !tr[j][t]) j = ne[j];
        if (tr[j][t]) j = tr[j][t];  //这一部分和get_fail函数基本一致
        int p = j;
        while (p) {  //这里主要是防止漏掉aba，ba这种由包含关系的情况
            ans += cnt[p];
            cnt[p] = 0;
            p = fail[p];
        }
    }
}

思路2

$Trie$ 图的话，就可以简单很多，具体看代码

代码2

void query (char s[M]) {
    for (int i = 0,j = 0;str[i];i++) {
        int t = str[i] - 'a';
        int p = j = tr[j][t];  //Trie图可以一步跳到位
        while (p) {  //这里主要是防止漏掉aba，ba这种由包含关系的情况
            ans += cnt[p];
            cnt[p] = 0;
            p = fail[p];
        }
    }
}

我都写了这么久，你还能不点赞吗？