AC 自动机学习笔记

AC 自动机是一种多模式串匹配算法，可以用来在文本串中匹配一系列模式串，其时间复杂度与串的总长度成正比。

引入

给一个 Trie 和一个文本串，求 Trie 上所有单词在文本串中的出现次数。

如果使用朴素的匹配算法，时间复杂度非常高。如果对 Trie 上每个单词使用 KMP 预处理后匹配，还是需要做次的匹配。

失配函数

我们知道，在 KMP 算法中，如果在模式串的一个位置失配，则需要回到模式串的前面一个位置继续匹配。从位置处失配后回到位置，记作。

考虑的条件 —— 串的前个字符组成的前缀，是前个字符组成前缀的后缀。理论依据是，这样可以保证每一时刻已匹配的字符尽量多，避免遗漏。

现在将问题转化为，在一棵 Trie 上，求一个节点，使得从根到的路径组成的串是从根到的路径组成串的后缀。

构造

AC 自动机

设父节点为，的入边上的字母为。

一个显然的结论是，如果有字母的出边，则该出边指向的点即为。例如，上图中。

如果没有字母的出边，则沿着失配函数继续向上找，找到 …… 直到找到根为止，如果找不到一个符合条件的节点，则为根。例如，上图中。

匹配

用于匹配字符串时，设置一个当前状态，它的初始值为根。每一次新加入一个字符，首先检查状态有没有出边，如果有，则转移到出边指向的点上，否则继续检查有无字符的出边。如果找不到满足条件的节点，则转移到根节点上。

如果状态转移到一个单词节点上，则代表这个单词被匹配到。但有时会出现，一个节点不是单词，是单词。

如下图，a 和 bac 组成的 AC 自动机（一些失配边已略去）。

节点 3 可以通过失配边连向 1，如果输入 ba 则会到达节点 3，节点 1 处的单词则被忽略。为了解决这一问题，我们引入另一个指针 —— 后缀链接，表示从节点沿着失配边转移，能到达的第一个单词节点，如上图。

有了后缀链接，便可以在匹配时检查每个节点的后缀链接，记录匹配单词时要遍历被匹配节点后缀链接。

后缀链接可以在失配指针之后求出 —— 如果为单词节点，则，否则。

优化

由于每次失配时需要使用失配指针，每次输入一个字符时经过的节点数不确定，时间复杂度可能会退化。

一个显然的结论是，对于一个状态，对它添加一个字符之后，转移到的状态是确定的。也就是说，我们可以预处理每一个状态可能转移到的所有状态。

对于节点，如果它有字符的出边，则在加入字符时，它可以直接转移到该出边指向的节点上。否则，应该转移到加入对应字符时转移到的点上。我们可以用递推的方式求出这些转移方式，并且在 Trie 树上加上这些边，得到Trie 图。

模板

统计每个模式串的出现次数。

更新于 2016 年 12 月 27 日。

const int CHARSET_SIZE = 'z' - 'a' + 1; // 字符集大小
const char BASE_CHAR = 'a'; // 最小的字符

struct Trie
{
    struct Node
    {
        Node *c[CHARSET_SIZE], *next, *fail;
        bool isWord;
        int ans;

        Node(bool isWord = false) : next(NULL), fail(NULL), isWord(isWord)
        {
            for (int i = 0; i < CHARSET_SIZE; i++) c[i] = NULL;
        }

        void apply()
        {
            ans++;
            if (next) next->apply();
        }
    } *root;

    Trie() : root(new Node()) {}

    Node *insert(const char *begin, const char *end)
    {
        // 插入过程类似 Splay
        Node **v = &root;
        for (const char *p = begin; p != end; p++)
        {
            // 向下找到对应节点的位置
            if (!*v) *v = new Node;
            v = &(*v)->c[*p];
        }
        if (!*v) *v = new Node(true);
        else (*v)->isWord = true;
        return *v;
    }

    void build()
    {
        std::queue<Node *> q;
        q.push(root);
        root->fail = root; // 边界
        root->next = NULL;
        while (!q.empty())
        {
            Node *v = q.front();
            q.pop();

            for (int i = 0; i < CHARSET_SIZE; i++)
            {
                // 使用引用减少代码量
                Node *&c = v->c[i];

                // 补全为 Trie 图
                if (!c)
                {
                    // 如果 v == root，则 v->fail == root，c 和 v->fail->c[i] 是同一个变量
                    c = v == root ? root : v->fail->c[i];
                    continue;
                }
                Node *u = v->fail;

                // 类似 KMP 的方法，求失配指针
                // while (u != root && !u->c[i]) u = u->fail; // 补全为 Trie 图，此行可省略

                // 如果 v == root，则失配后一定回到根节点
                c->fail = v != root && u->c[i] ? u->c[i] : root;

                // 沿着 fail 指针能走到的第一个单词节点
                c->next = c->fail->isWord ? c->fail : c->fail->next;
                q.push(c);
            }
        }
    }

    void exec(const char *begin, const char *end)
    {
        Node *v = root;
        for (const char *p = begin; p != end; p++)
        {
            // 状态转移
            v = v->c[*p];

            // 统计答案
            if (v->isWord) v->apply();
            else if (v->next) v->next->apply(); // 注意是 else if
        }
    }
};