AC 自动机的一些匹配板子

wing_heart · 2025-11-03 20:00:24 · 算法·理论

AC 自动机的一些匹配板子

原文链接

AC 自动机介绍

参考 OI-Wiki AC 自动机。

如果你已经会 AC 自动机（包括 fail 树的构建），可以跳过这部分。

自动机

参考 OI-Wiki 有限状态自动机。

支持的功能

AC 自动机可以对多个 s 建自动机，然后查询哪些 s 是 t 的字串。

但是建好之后似乎不支持再插入新串。

建树流程概括

1. 建出 trie 树。

   把所有 s 插入 trie。字符串从前往后插入。

2. 构建适配指针 fail。

struct node {
    int fail;
    // int tg;
    int son[26];
}tr[N];
int cnt;
void insert(char *s,int n) { // 在字典树中插入串串 s
    int u = 0;
    rep(i,0,n-1) {
        int c = s[i]-'a';
        if(!tr[u].son[c]) tr[u].son[c] = ++cnt;
        u = tr[u].son[c];
    }
    // 更新 tr[u]
}
void build() { // 建 fail 树
    // 若 rt 非 0，则需要把 tr[rt] 的所有空儿子，和 tr[rt].fail 设成 rt
    queue<int> que;
    rep(i,0,25) if(tr[0].son[i]) que.push(tr[0].son[i]); // tr[tr[0].son[i]].fail = rt
    while(que.size()) {
        int u = que.front();
        que.pop();
        rep(i,0,25) {
            if(tr[u].son[i]) {
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                que.push(tr[u].son[i]);
            } else tr[u].son[i] = tr[tr[u].fail].son[i];
        }
    }
}

怎么构建失配指针？

按照 bfs 的顺序求 fail_u。

现在 dep_x < dep_u 的 fail_x 都已经求好。要求 fail_u。fa_u 经过边 c 到达 u。

• 若 fail_{fa_{u}} 经过 c 可以到达状态 v，则 fail_u = v。
• 否则，递归查 fail_{fail_{fa_u}}。
• 以此类推。

特判 fail 指向根节点的时候。

欸，它的时间复杂度是多少？

跳 fail 的次数是 O(L) 的，L 是所有字符串的长度之和。不过找出边的时候可能需要和字符集大小有关的复杂度。

具体怎么证明？

可以用势能分析一下吧，势能定义为在队列里的 u（因为只有这些 u 才会需要跳 fail），\sum dep_{fail_u}。

跳 fail 的时候会消耗势能。求出 fail_u 之后，u 的儿子会继承 u 的势能。假如 u 有 k 个儿子，那么节点个数就会相对 L 减少 (k-1)dep_u。

所以总共消耗掉的势能是 O(L) 的。

因为每个点只有一个 fail 指针，且指向 dep 严格小于它的点，所以所有 fail 指针形成一棵 fail 树。

代码见上面。

多模式匹配

对于字典 \{s_i\}，找有多少 s 是 t 的子串。

顺序枚举 t 的每个字符，当前在状态 u，要经过字母 c 去到下一个状态。

• 遍历 u 在 fail 树上到根的 fail 链，找到所有后缀状态，加进答案。
• 如果原 trie 上 u 经过 c 可以到达 v，就直接走了。
• 否则看看 fail_u 能否经过 c 到达 v。
• 否则跳下一个适配指针。

复杂度最坏是 O(L^2) 的。

需要优化。

求哪些 s_i 在 t 中出现了

这个不用优化，直接暴力跳 fail 指针，不要跳已经跳过的节点即可。

P3808 AC 自动机（简单版），code。

求每个 s_i 在 t 中出现多少次

在 AC 自动机里面跑 t 的时候，记录每个状态遇到的次数 tag。

1. 最后对 fail 树拓扑排序（内向树）。然后按照拓扑序记录答案。
2. 也可以 dfs，按照 dfs 序逆序更新答案，或者递归回溯的时候更新答案。

只是不同的写法而已。

P5357 【模板】AC 自动机，code。

对每个 t_i，求所有 s 在 t_i 中出现次数之和

每个状态 u 的权值 w_u 是以 u 为终点的 s 的个数。预处理出 u 在 fail 树上到根的和 sw_u。

然后跑 t 的时候，每个状态加上它的 sw_u。

类似题目：P14363 [CSP-S 2025] 谐音替换 / replace，code。

对每个 t_i，求有多少 s 是它的字串

类似题目：P2336 [SCOI2012] 喵星球上的点名

https://www.luogu.com.cn/discuss/1190105

1. 简单的哈希做法，复杂度根号。按照字符串长度分类，一共只有根号种不同的长度。然后分类哈希。https://www.luogu.com.cn/article/zevrys8n
2. 单老哥做法。跑 t 的时候每个状态 u 需要记录 u 在 fail 树上到根的链中，没有被算过的点。可以使用重链剖分维护每个重链的哪个前缀以及使用过；或者建所有 u 的虚树，然后在虚树上面统计，怎么统计都行吧。

对每个 s_i，求它在几个 t_i 中出现了

类似题目：P5840 [COCI 2014/2015 #5] Divljak

跑 t 的时候建出 u 的虚树。把 u 按照 dfs 序排序，然后在虚树上面打差分标记。最后统一前缀和标记。

上面的例题，每个 t 只能对 k 个点贡献，\sum k = q。所以需要每个虚树在线 O(len+k) 更新贡献。可以在虚树上差分，在 dfs 序上用树状数组维护子树和，和单点查询。于是这个板子也可以在线做。

对每个 s_i，求它在所有 t_i 出现的次数之和

跑 t 的时候维护树上差分标记。最后统一前缀和求出答案。