AC Automaton

记录AC自动机算法的学习。

回顾KMP算法

对于一个字符串$s$，每一位的下标为$1, 2, \cdots, n$，则我们可以求出一个数组$p$，满足以下约定：

设$s_i$表示$s$前$i$个字符构成的子串；
$p_i$表示$s_i$的子串（不包括$s_i$自身）中，最长的、且同时为$s_i$的前后缀的子串长度。

这样的定义同时保证了$p_i$指向了$s_i$的最长前后缀的最后一个字符。

考虑用$O(n)$时间求出这个$p$数组：

假设$p_0 = 0$，且$p_0, p_1, \cdots, p_{i - 1}$都已经求好，那么我们如下方法求$p_i$：

1. 令$j = p_{i - 1}$
2. 如果$j+1$对应的字符和$i$对应的字符相等，那么$p_i$就是$j+1$；
3. 如果不满足(2)，且$j=0$，则$p_i=0$；
4. 如果(2)(3)均不满足，则$j\leftarrow p_j$，回到(2)。

这样做的正确性是：

1. 首先$p_i \leq p_{i - 1} + 1$，因为只要定了$p_i$，则往前推一格就能得到$p_{i-1}$的下界；
2. 同理，当$p_{i-1}+1$和$i$对应的字符不相等时，$p_i\leq p_{p_{i - 1}} + 1$；
3. 以此类推，所以只要不停地往前迭代$p$即可。

复杂度正确性：

$p$每次最多增加$1$，往前迭代过程中$j$每次最少减少$1$，所以总共最多迭代$n$次。

参考代码（【模板】KMP）

注意特判$i=1$的情况，否则会$p_i = i$。

Show Code

#include <iostream>
#include <vector>
signed main() {
    std::string s1, s2; std::cin >> s1 >> s2;
    s1 = '.' + s1;
    s2 = '.' + s2;
    const int m = s1.length() - 1;
    const int n = s2.length() - 1;
    std::vector<int> p(n + 1, 0);
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j && s2[j + 1] != s2[i]) j = p[j];
        if (j + 1 != i && s2[j + 1] == s2[i]) p[i] = ++j; 
    }
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j && s2[j + 1] != s1[i]) j = p[j];
        if (s2[j + 1] == s1[i]) ++j;
        if (j == n) (std::cout << (i - j + 1) << std::endl), j = p[j];
    }
    for (int i = 1; i <= n; ++i) {
        std::cout << p[i] << ' ';
    }
    std::cout << std::endl;
    return 0;
}

## AC自动机

问题引入

假设现在有$n$个字符串$s_1, s_2, \cdots, s_n$，要判断每个字符串是否是字符串$t$的子串。

如果用KMP算法，对于$n$个字符串求失配指针$p$，复杂度为$O(n\sum \left|s_i\right|)$；分别跟$t$匹配，复杂度为$O(\sum \left|t\right|) = O(n\left|t\right|)$，复杂度为$O(n(\sum \left|s_i\right| + \left|t\right|))$，当$\left|t\right|$很大时就GG了。

AC自动机算法

搞一个Trie，把所有$s_i$都丢进去，其中根节点编号为$0$，设点$u$的子节点中，连着字符$c$的子节点为$ne_{u, c}$，没有则是$0$。

然后我们模仿KMP对字典树上每个节点求失配指针$p$。在树上进行一个BFS，每次求$v$节点的$p$时，深度小于$v$的节点都已经求好了。设$u$是$v$的父亲，$(u,v)$边对应字符为$c$，那么我们不停的找到$p_u$，如果$ne_{p_u, c}$存在，那么就找到了，否则一直取$p$。这样就可以找到所有点的$p$。

匹配的时候，如果$u$的下一个失配了，那么我们就跳到$p_u$继续尝试匹配。

复杂度分析

建树这一步复杂度为$O(nm\times\sum\left|s_i\right|)$，其中$m$表示字符数量。

但是求解失配指针的这一步好像炸缸了，可能会被卡到平方级（每次都往前跳$O(n)$下），但不知道为啥过了。

为了优化求失配指针的过程，我们不能再一直往前跳了，但是匹配的时候，由于要匹配的东西是一个线性结构，依然满足之前的均摊复杂度，只要保证每次跳完长度至少$-1$即可。

回顾一下需要往前继续跳的情况：$ne_{p_u, c}=0$。反正空着也是空着，我们不妨让$ne_{p_u, c}=ne_{p_{p_u}, c}$，这样就有个很有意思的结果：如果$ne$不存在，那么$ne$会指向第一个存在的失配指针，因为如果它指向的也不存在，那么那个不存在的会指向一个存在的（归纳）。

这样处理之后，我们就不需要跳了，直接设$p_v = ne_{p_u, c}$就好了。

这样求解失配指针的复杂度就优化到了$O(nm\sum\left|s_i\right|)$。

最后就是查询。以此题为例。

首先可以想到在每个trie的节点上开一个vector记录当前节点是哪些字符串的结尾。

对$t$进行匹配，目标字符串$t$对于第$i$位匹配到节点$u$，则表示到$u$节点的路径的所有后缀都可以匹配到第$i$位。给节点$u$打上标记vis[u]++，最后我们希望所有的$p_u, p_{p_u}, \cdots$都可以继承vis[u]。

直接暴力跳会和之前一样复杂度爆炸，不如用拓扑排序（$p$数组建成的图当然是一个DAG）。

这样查询的复杂度是$O(\left|t\right|)$。

修改后也没快多少。

总的时间复杂度：$O(nm\sum\left|s_i\right|+\left|t\right|)$，如果$m$可视为常数（比如说26），则复杂度是$O(n\sum\left|s_i\right| + \left|t\right|)$，比KMP快，尤其是在$\left|t\right|$比较大的情况下。

但是当$m$不可忽略时还有待研究。可能可以使用类似map的东西，带一个$\log$的复杂度。

参考代码

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>

const int M = 26;
class acAutomaton {
private:
    std::vector<std::vector<int> > ne;
    std::vector<std::vector<int> > end;
    std::vector<int> p;
    int idx = 0;
    int num = 0;
    int add() {
        ne.push_back(std::vector<int>(M, 0));
        end.push_back(std::vector<int>());
        return idx++;
    }
    void calcPre() {
        p.resize(idx);
        p[0] = 0;
        std::queue<int> q;
        for (int i = 0; i < M; ++i) {
            if (ne[0][i]) q.push(ne[0][i]);
            // 注意，直接插入根节点会出现和KMP一样的问题
        }

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < M; ++i) {
                int& v = ne[u][i];
                if (v) {
                    p[v] = ne[p[u]][i]; // 上一个可以的地方
                    q.push(v);
                } else {
                    v = ne[p[u]][i]; // 直接插到上一个可以的地方
                }
            }
        }

        // for (int i = 0; i < idx; ++i) {
        //     // for (int j = 0; j < M; ++j) {
        //     //     printf("i = %d, j = %d, ne = %d\n", i, j, ne[i][j]);
        //     // }
        //     // printf(">>i = %d, p = %d\n", i, p[i]);
        // }
    }
public:
    acAutomaton() {add(); }
    void addToTrie(const std::string& s) {
        int now = 0;
        for (const char& c : s) {
            if (!ne[now][c - 'a']) ne[now][c - 'a'] = add();
            now = ne[now][c - 'a'];
            // end[now] = (&c == &s.back() ? ++num : 0);
            if (&c == &s.back()) end[now].push_back(num++);
            // if (end[now]) printf("end %d = %d\n", now, end[now]);
        }
    }
    std::vector<int> calc(const std::string& t) {
        calcPre();
        std::vector<int> vis(idx, 0);
        int u = 0;
        for (const char c : t) {
            while (u && !ne[u][c - 'a']) u = p[u];
            u = ne[u][c - 'a'];
            vis[u] ++;
        }

        // for (int i = 1; i < idx; ++i) {
        //     int j = i;
        //     if (!vis[j]) continue;
        //     while (p[j]) j = p[j], vis[j] += vis[j];
        // }

        std::vector<int> d(idx, 0);
        std::queue<int> q;
        for (int i = 1; i < idx; ++i) {
            d[p[i]]++;
        }
        for (int i = 1; i < idx; ++i) {
            if (!d[i]) q.push(i); 
        }
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (!u) continue;
            int v = p[u];
            vis[v] += vis[u];
            --d[v];
            if (!d[v]) q.push(v);
        }

        std::vector<int> res(num);
        for (int i = 1; i < idx; ++i) {
            // printf("vis[%d] = %d\n", i, vis[i]);
            if (end[i].empty()) continue;
            for (const int j : end[i]) res[j] = vis[i];
        }
        return res;
    }
};

signed main() {
    int n; std::cin >> n;
    acAutomaton T;
    for (int i = 0; i < n; ++i) {
        std::string s; std::cin >> s;
        T.addToTrie(s);
    }
    std::string t; std::cin >> t;
    for (const auto x : T.calc(t)) std::cout << x << std::endl;
    return 0;
}