专栏文章

AC 自动机的一些匹配板子

wwing_heart
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mine40ph
此快照首次捕获于
2025/12/02 00:55
3 个月前
此快照最后确认于
2025/12/02 00:55
3 个月前
查看原文

AC 自动机的一些匹配板子

原文链接

AC 自动机介绍

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

自动机

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

支持的功能

AC 自动机可以对多个 ss 建自动机，然后查询哪些 ss 是 tt 的字串。
但是建好之后似乎不支持再插入新串。

建树流程概括

  1. 建出 trie 树。
    把所有 ss 插入 trie。字符串从前往后插入。
  2. 构建适配指针 failfail。
    failufail_u 指向 vv，状态 vv 是 uu 的后缀，且长度最长。
CPP
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 的顺序求 failufail_u。
现在 depx<depudep_x < dep_u 的 failxfail_x 都已经求好。要求 failufail_u。faufa_u 经过边 cc 到达 uu。
  • 若 failfaufail_{fa_{u}} 经过 cc 可以到达状态 vv，则 failu=vfail_u = v。
  • 否则，递归查 failfailfaufail_{fail_{fa_u}}。
  • 以此类推。
特判 failfail 指向根节点的时候。
欸，它的时间复杂度是多少？
跳 failfail 的次数是 O(L)O(L) 的，LL 是所有字符串的长度之和。不过找出边的时候可能需要和字符集大小有关的复杂度。
具体怎么证明？
可以用势能分析一下吧，势能定义为在队列里的 uu（因为只有这些 uu 才会需要跳 failfail），∑depfailu\sum dep_{fail_u}。
跳 failfail 的时候会消耗势能。求出 failufail_u 之后，uu 的儿子会继承 uu 的势能。假如 uu 有 kk 个儿子，那么节点个数就会相对 LL 减少 (k−1)depu(k-1)dep_u。
所以总共消耗掉的势能是 O(L)O(L) 的。
因为每个点只有一个 failfail 指针，且指向 depdep 严格小于它的点，所以所有 failfail 指针形成一棵 failfail 树。
代码见上面。

多模式匹配

对于字典 {si}\{s_i\}，找有多少 ss 是 tt 的子串。
顺序枚举 tt 的每个字符，当前在状态 uu，要经过字母 cc 去到下一个状态。
  • 遍历 uu 在 failfail 树上到根的 failfail 链，找到所有后缀状态，加进答案。
  • 如果原 trie 上 uu 经过 cc 可以到达 vv，就直接走了。
  • 否则看看 failufail_u 能否经过 cc 到达 vv。
  • 否则跳下一个适配指针。
复杂度最坏是 O(L2)O(L^2) 的。
需要优化。

求哪些 sis_i 在 tt 中出现了

这个不用优化，直接暴力跳 fail 指针，不要跳已经跳过的节点即可。
P3808 AC 自动机（简单版），code。

求每个 sis_i 在 tt 中出现多少次

在 AC 自动机里面跑 tt 的时候，记录每个状态遇到的次数 tagtag。
  1. 最后对 failfail 树拓扑排序（内向树）。然后按照拓扑序记录答案。
  2. 也可以 dfs，按照 dfs 序逆序更新答案，或者递归回溯的时候更新答案。
只是不同的写法而已。
P5357 【模板】AC 自动机，code。

对每个 tit_i，求所有 ss 在 tit_i 中出现次数之和

每个状态 uu 的权值 wuw_u 是以 uu 为终点的 ss 的个数。预处理出 uu 在 failfail 树上到根的和 swusw_u。
然后跑 tt 的时候，每个状态加上它的 swusw_u。
类似题目：P14363 [CSP-S 2025] 谐音替换 / replace，code。

对每个 tit_i，求有多少 ss 是它的字串

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

对每个 sis_i，求它在几个 tit_i 中出现了

类似题目：P5840 [COCI 2014/2015 #5] Divljak
跑 tt 的时候建出 uu 的虚树。把 uu 按照 dfs 序排序，然后在虚树上面打差分标记。最后统一前缀和标记。
上面的例题，每个 tt 只能对 kk 个点贡献，∑k=q\sum k = q。所以需要每个虚树在线 O(len+k)O(len+k) 更新贡献。可以在虚树上差分，在 dfs 序上用树状数组维护子树和，和单点查询。于是这个板子也可以在线做。

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

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...