AC 自动机学习笔记

· · 个人记录

P3808 【模板】AC自动机（简单版）

给定 n 个模式串 s_i 和一个文本串 t，求有多少个不同的模式串在文本串里出现过。

题意可以转化为：有多少模式串是文本串的子串。

子串不就是前缀的后缀吗？

对模式串建立 \text{trie} 树，那么 \text{trie} 树上一个节点 x 保存的信息就是某个模式串的前缀，我们把其称为一个状态 S(x)。

考虑枚举文本串的一个前缀 P_i，在 \text{trie} 树上找一个节点 p_i 使得 S(p_i) 为 P_i 的后缀且极长，那么我们如果可以在树上再遍历所有 x 使得 S(x) 为 S(p_i) 的后缀，则能确定所有文本串前缀在树上的后缀。

考虑对于 \text{trie} 树上节点 x 预处理一个 \mu(x) 使得 S(\mu(x)) 为 S(x) 的后缀且极长，那么所有使得 S(y) 为 S(x) 后缀的 y 的集合为 : \{\mu(x),\mu(\mu(x)),\cdots,root\} ,我们称其为 x 的树上后缀集合 suf(x)。

引入转移的概念：我们称 \text{trie} 树上节点 x 对字符 c 的转移 M(x,c) 为：S(M(x,c)) 为 S(x) +c 的后缀且 S(M(x,c)) 极长。显然，如果 \text{trie} 树已经有节点 x 添加字符 c 的儿子 y，则有 M(x,c) =y 。如果没有对于字符 c 的儿子，那么则为 z\in suf(x)， S(z) 极长且有对于字符 c 的儿子，如果所有在 suf(x) 中的节点都没有的话则为 root，易得：

\begin{cases} son_{x,c}& son_{x,c}\neq0\\ M(\mu(x),c)& son_{x,c}=0 \end{cases}

显然，通过这样的转移我们可以建立一个 \text{trie} 图，把 x 与其所有转移相连即可。通过这样一个 \text{trie} 图，如果我们知道了前缀 a 与其对应的图中节点 p_a 使得 S(p_a) 为 P_a ，想求前缀 p+1 对应的节点 p_{a+1}，那么 p_{a+1} = M(p_a,c)，其中 c 为文本串中第 a+1 位的字符。这个转移的意义即是把前缀 P_a 的图中极长后缀 p_a 后添加一个 c 的图中极长后缀，与转移的意义相符。

我们考虑怎么求出 \mu(x)：

显然有，如果知道 \mu(fa_x)，那么 S(x) 树上极长后缀即为父亲的极长后缀对节点 x 对应字符 c_x 的转移 M(\mu(fa_x), c_x)。 可以理解为：爸爸添加字符 c_x 的最长后缀就相当于爸爸最长后缀加入字符 c_x 的最长后缀。

那么通过一遍 bfs 则可以把 \text{trie} 树转化为 \text{trie} 图并预处理好 \mu。

比较时即可通过 O(1) 的转移 p_i 并遍历 suf(p_i) 即可遍历前缀 P_i 在树上的所有后缀。最后则可以遍历完所有文本串的树上子串。在遍历的过程中加上以遍历点为结尾的模式串数即可。

放个代码：

#include <stdio.h>
#include <queue>
#include <string>
#include <iostream>
#define Maxn 1000005
#define Rep(i, l, r) for(i = l; i <= r; ++ i)

int n;

struct acm{
    int m[Maxn][26], cnt[Maxn], mu[Maxn], tot;
    std :: queue <int> q;

    void ins(std :: string s) {
        int len = s.length(), x, y;

        for(x = 0, y = 0; y < len; ++ y) {
            if(! m[x][s[y] - 'a']) m[x][s[y] - 'a'] = ++ tot;
            x = m[x][s[y] - 'a'];
        }

        ++ cnt[x];
    }

    void build() {
        int i, u, v;
        Rep(i, 0, 25) if(m[0][i]) q.push(m[0][i]);

        while(! q.empty()) {
            u = q.front(), q.pop();
            Rep(v, 0, 25) {
                if(m[u][v]) mu[m[u][v]] = m[mu[u]][v], q.push(m[u][v]); //处理儿子的 mu
                else m[u][v] = m[mu[u]][v]; // 继承下转移 
            }
        }
    }

    int match(std :: string s) {
        int len = s.length(), ans = 0;
        for(int x = 0, y = 0, u; y < len; ++ y) {
            x = m[x][s[y] - 'a']; 

            for(int v = x; v && cnt[v] != -1; v = mu[v]) {
                ans += cnt[v];
                cnt[v] = -1;
            } 
        }
        return ans;
    }
}T;

int main() {
    int i;
    std :: string s;
    scanf("%d", &n);
    Rep(i, 1, n) std :: cin >> s, T.ins(s);
    T.build(); std :: cin >> s;
    printf("%d", T.match(s));
}

updated on 2023.10.20

感觉写的还行，好像是我前期写的最有感觉的一篇。