AC 主动机具体剖析

AC主动机剖析

前置知识

Trie 字典树 KMP
发起彻底明白 Trie，这很告急。
先容

AC 主动机（ACAM）是一种实现多模匹配的主动机（Automaton），将 KMP 头脑和 Trie 融合起来，可以在 \(O(|s|+\sum|t_i|)\) 的时间，\(O(|s|+\sum|t_i|)\) 的空间内完成多模匹配。
原理

Fail 指针

这里的 Fail 指针和 KMP 的失配树中的 \(next\) 数组照旧有区别的。KMP 的 \(next\) 指针是 Border，也就是最长雷同真前后缀。而这里的 Fail 指针是指向最长的在 Trie 里的真后缀。
匹配

表示图：

此中插入的模式串为：\(t_1=\texttt{AB},t_2=\texttt{ABB},t_3=\texttt{ABC},t_4=\texttt{BC},t_5=\texttt{CA},t_6=\texttt{CBB},t_7=\texttt{CC}\)，此中圈出的为 Trie 树上的标记。文本串是 \(s=\texttt{ABBCABACBCC}\)。
如果直接匹配就会发现当匹配到第三个字符时，刚好匹配上，此时匹配次数加一。然后呢？只能从根继续匹配。
我们想到优化：我们可以直接从最长的在 Trie 里的真后缀开始继续匹配，由于如许可以省去了前面的匹配，直接从 Fail 指针处继续。
如果没有在 Trie 里的真后缀怎么办？这就要从根开始了，也就是重新匹配。
匹配失败了也一样，跳 fail 直到回到根。
算法流程

以洛谷 P3808 AC 主动机（简朴版）为例讲授。
建立

就是 Trie 自己的建立。不会可以去搜索一下。
代码：

1. void insert(const string &t) {
2.         int now = 1;
3.     for(auto &c : t) {
4.         if(!trie[now].son[c - 'a']) trie[now].son[c - 'a'] = ++tc;
5.         now = trie[now].son[c - 'a'];
6.     }
7.     trie[now].flg++;
8. }

复制代码

求 fail 指针

方便表述，记 \(Fail_u\) 是 \(u\) 的 fail 指向的节点，\(S_u\) 是 \(u\) 指向的串。
我们可以发现两个性子：

• 真后缀的的真后缀是真后缀。
  
• 如果一个节点 \(u\) 和 \(Fail_u\) 都有一个雷同儿子 \(i,i\in\{\texttt{A},\dots,\texttt{Z}\}\)，那么 \(S_{Fail_u}+i\)（ \(+\) 表现字符串拼接）就是\(s_u+i\) 的最长的在 Trie 里的真后缀。
  

以是我们就可以从深度小的串求出深度大的串的 fail 指针。我们发现这就雷同 Trie 上 BFS。具体流程如下：

• 在访问到一个节点 \(u\) 的时间，遍历全部存在的子节点。
  
• 如果 \(u\) 的 fail 也有这个子节点，就直接将这个儿子的 fail 指向 \(u\) 的 fail 的这个子节点。否则重复跳直到根。
  

我们思量继续优化。这里有一个本领：路径压缩。
我们可以发现 \(Fail_u\) 总是在 \(u\) 之前盘算，那我们就可以直接不管对方有没有这个子节点，就直接挂上去，也就是挂到 \(Fail_u\) 跳 fail 之后的节点。这就可以制止构建时每次跳 fail。
同样的，在 \(u\) 原来就没有的子节点，就可以直接挂到 \(Fail_u\) 的子节点上。如许在失配的时间就可以直接跳 fail 了。
为了搞定根节点的环境，我们规定  \(Fail_{root} = 0\)，\(0\) 的全部子节点都是根。如许我们在更新第一层的时间，fail 就是 \(0\) 的儿子也就是根。
代码：

1. void build() {
2.     queue<int> q;
3.     for(int i = 0; i < 26; i++) trie[0].son[i] = 1;
4.     q.push(1), trie[1].fail = 0;
5.     while(!q.empty()) {
6.         int fa = q.front(); q.pop();
7.         for(int i = 0; i < 26; i++) {
8.             int &son = trie[fa].son[i];
9.             int fafail = trie[fa].fail;
10.             if(!son) {son = trie[fafail].son[i]; continue;} // 没有的子节点直接跳 fail
11.             trie[son].fail = trie[fafail].son[i]; // 直接挂上去即可
12.             q.push(son);
13.         }
14.     }
15. }

复制代码

查询

着实就是前面的匹配，但加入了路径压缩，在失配时就可以直接跳了。

1. int query(const string &s) {
2.     int ans = 0, u = 1;
3.     for(auto &_ : s) {
4.         int c = _ - 'a', v = trie[u].son[c];
5.         while(v > 1 && trie[v].flg != -1) { // 不断跳 fail，算过就不算了
6.             ans += trie[v].flg; trie[v].flg = -1;
7.             v = trie[v].fail;
8.         }
9.         u = trie[u].son[c];
10.     }
11.     return ans;
12. }

复制代码

代码

[code]#include using namespace std;using ll = long long;const int N = 1e6 + 5;struct ACAM {    struct Node {        int son[26], fail, flg;    } trie[N];    int tc = 1;    void insert(const string &t) {        int now = 1;        for(auto &c : t) {            if(!trie[now].son[c - 'a']) trie[now].son[c - 'a'] = ++tc;            now = trie[now].son[c - 'a'];        }        trie[now].flg++;    }    void build() {        queue q;        for(int i = 0; i < 26; i++) trie[0].son = 1;        q.push(1), trie[1].fail = 0;        while(!q.empty()) {            int fa = q.front(); q.pop();            for(int i = 0; i < 26; i++) {                int &son = trie[fa].son;                int fafail = trie[fa].fail;                if(!son) {son = trie[fafail].son; continue;}                trie[son].fail = trie[fafail].son;                q.push(son);            }        }    }    int query(const string &s) {        int ans = 0, u = 1;        for(auto &_ : s) {            int c = _ - 'a', v = trie.son[c];            while(v > 1 && trie[v].flg != -1) {                ans += trie[v].flg; trie[v].flg = -1;                v = trie[v].fail;            }            u = trie.son[c];        }        return ans;    }}acam;int main() {    ios::sync_with_stdio(0), cin.tie(0);    int n; cin >> n;    for(int i = 1; i > t;        acam.insert(t);    }    acam.build();    string s; cin >> s;    cout