AC 自动机（Aho–Corasick automaton）是一种将 Trie 和 KMP 算法两者结合的自动机，用于多个模式串的同时匹配。

概述

概念

AC 自动机，在 Trie 的基础上连接新的边得到。其节点（状态）与 Trie 相同，但是不同于 Trie 的不匹配就直接推出，AC 自动机的每个节点接受一个字符后，都会转移到新的节点上。

如何判断一个节点匹配失败后应该转移到哪里呢？我们可以记录：这个节点所对应字符串，在 Trie 中的能找到的最长真后缀对应的节点，并用指针 fail 表示。这个概念非常类似于 （链接未公开） 的 border，实际上，KMP 的状态可以看做退化成链的 Trie，此时最长真后缀就等同于 border。

例如，字符串 abab、abc、bca、cc 形成的 Trie 如下图，则其中蓝色箭头表示 fail 边。

AC 自动机还可以进一步进行路径压缩。实际上，当 fail 边确定后，读入一个字符 c 后仍然可能沿 fail 边跳转多次才找到下一个匹配点（像 KMP 算法那样）。对每个节点 i，我们可以直接记录所有可能字符 c 对应的下一个节点，记录为数组 next，这里用 \operatorname{next}(i, c) 表示。

建立

当 p 不为根节点时，有

特殊地，对根节点 r 有 \operatorname{fail}(\operatorname{next}(r, c)) = r。而 fail 边一定指向深度更小的节点，依据此公式，在 Trie 上层次遍历一次，就可以同时处理出 AC 自动机的 next 和 fail 指针。

建树的代码如下：

void ac_build()
{
    rt.fail = &rt;
    queue<Node*> qu;
    qu.push(&rt);
    while (!qu.empty())
    {
        Node *u = qu.front();
        qu.pop();
        for (size_t i = 0; i < CHAR_SIZE; i++)
        {
            Node *&v = u->next[i];
            if (v == nullptr)
            {
                if (u == &rt)
                {
                    v = u;
                }
                v = u->fail->next[i];
                continue;
            }
            if (u == &rt)
            {
                v->fail = u;
            }
            else
            {
                v->fail = u->fail->next[i];
            }
            qu.push(v);
        }
    }
}