算法复键——AC自动机

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162074359

什么是AC自动机：

在Trie上跑kmp

核心思想：构建fail树。fail[u]指向一个节点，表示这个节点具有和u所在节点所代表串的最长公共后缀。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void bfs() {
	int i, j; 
	q.push(1); fail[1] = 0; fail[0] = 1; // 根节点失配指向0，0的fail拉回1
	while(!q.empty()) {
		int u = q.front(), v, k; q.pop(); 
		// 遍历26个字母，处理u所有存在的子节点v
		for(i = 0; i < 26; ++i) {
			if(!(v = ch[u][i]) || fail[v]) continue; 
			k = fail[u]; // k是u的失配祖先，对应KMP的next回跳
			// 找v的fail：沿着u的fail找是否有同字母子节点
			fail[v] = (ch[k][i] ? ch[k][i] : 1); 
			// 路径压缩优化：不存在的子节点直接赋值为fail链上对应节点
			for(j = 0; j < 26; ++j)
				if(!ch[v][j]) ch[v][j] = ch[fail[v]][j]; 
			q.push(v); 
			G[fail[v]].pb(v); // 反向建fail树边：fail[v]是v的父节点
		}
	}
}

  1. 初始化根
    根节点 u=1 入队， fail[1]=0 ；虚拟节点0的 fail[0]=1 ，防止无限回跳。

  2. 取出队首节点 u ，遍历26个字母，找到真实存在的子节点 v=ch[u][i]

  3. 求 fail[v] （KMP核心逻辑）

  • k = fail[u] ：跳到u的最长后缀节点

  • 如果 ch[k][i] 存在，说明这个后缀节点有相同字母子节点， fail[v]=ch[k][i]

  • 不存在则回退到根1， fail[v]=1
    等价KMP：匹配失败时，找最长相等前后缀起点

  1. 路径压缩（重要优化）
1
if(!ch[v][j]) ch[v][j] = ch[fail[v]][j];

正常AC不压缩：匹配时要循环跳fail找子节点；
你这里预处理填满所有 ch[v][j] ，之后 run 遍历文本时 不需要回跳fail ，直接 ch[u][c] 一步到位，省去循环，速度更快。
5. 建fail树 G ： G[fail[v]].push_back(v) ，把所有后缀关系存成树，用于后序统计。