AC 自动机

简介

AC 自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的。

简单来说，建立一个 AC 自动机有两个步骤：

1. 基础的 Trie 结构：将所有的模式串构成一棵 Trie。
2. KMP 的思想：对 Trie 树上所有的结点构造失配指针。

然后就可以利用它进行多模式匹配了。

构建字典树

AC 自动机在初始时会将若干个模式串丢到一个 Trie 里，然后在 Trie 上建立 AC 自动机。这个 Trie 就是普通的 Trie，该怎么建怎么建。

这里需要仔细解释一下 Trie 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。Trie 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，Trie 的边就是状态的转移。

形式化地说，对于若干个模式串 $s_{1}, \ s_{2}, \ \cdots, \ s_{n}$，将它们构建一棵字典树后的所有状态的集合记作 $Q$。

失配指针

AC 自动机利用一个 fail 指针来辅助多模式串的匹配。

状态 $u$ 的 fail 指针指向另一个状态 $v$，其中 $v \ \in \ Q$，且 $v$ 是 $u$ 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。fail 指针与 KMP 中的 next 指针：

• 共同点：两者同样是在失配的时候用于跳转的指针。
• 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。

AC 自动机的失配指针指向当前状态的最长后缀状态

AC 自动机在做匹配时，同一位上可匹配多个模式串。

构建指针

下面介绍构建 fail 指针的基础思想（强调！基础思想！基础！）：

构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想。

考虑字典树中当前的结点 $u$ ，$u$ 的父结点是 $p$，$p$ 通过字符 c 的边指向 $u$，即 trie[p, c] = u。假设深度小于 $u$ 的所有结点的 fail 指针都已求得。

1. 如果 trie[fail[p], c] 存在：则让 u 的 fail 指针指向 trie[fail[p], c]。相当于在 $p$ 和 fail[p] 后面加一个字符 c，分别对应 $u$ 和 fail[u]。
2. 如果 trie[fail[p], c] 不存在：那么我们继续找到 trie[fail[fail[p]], c]。重复 1 的判断过程，一直跳 fail 指针直到根结点。
3. 如果真的没有，就让 fail 指针指向根结点。

如此即完成了 fail[u] 的构建。

字典树与字典图

构建

该函数的目标有两个，一个是构建 fail 指针，一个是构建自动机。参数如下：

1. tr[u,c]：有两种理解方式。我们可以简单理解为字典树上的一条边，即 trie[u, c]；也可以理解为从状态（结点）$u$ 后加一个字符 c 到达的状态（结点），即一个状态转移函数 trans(u, c)。下文中我们将用第二种理解方式继续讲解。
2. 队列 q：用于 BFS 遍历字典树。
3. fail[u]：结点 $u$ 的 fail 指针。

void build()
{
	for (int i = 0; i < 26; i++)
		if (tr[0][i]) q.push(tr[0][i]);
	while (q.size())
	{
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; i++)
		{
			if (tr[u][i])
				fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
			else
				tr[u][i] = tr[fail[u]][i];
		}
	}
}

解释一下上面的代码：build 函数将结点按 BFS 顺序入队，依次求 fail 指针。这里的字典树根结点为 0，我们将根结点的子结点一一入队。若将根结点入队，则在第一次 BFS 的时候，会将根结点儿子的 fail 指针标记为本身。因此我们将根结点的儿子一一入队，而不是将根结点入队。

然后开始 BFS：每次取出队首的结点 u（fail[u] 在之前的 BFS 过程中已求得），然后遍历字符集（这里是 0-25，对应 a-z，即 $u$ 的各个子节点）：

1. 如果 trans[u][i] 存在，我们就将 trans[u][i] 的 fail 指针赋值为 trans[fail[u]][i]。这里似乎有一个问题。根据之前的讲解，我们应该用 while 循环，不停的跳 fail 指针，判断是否存在字符 i 对应的结点，然后赋值，但是这里通过特殊处理简化了这些代码。
2. 否则，令 trans[u][i] 指向 trans[fail[u]][i] 的状态。

这里的处理是，通过 else 语句的代码修改字典树的结构。没错，它将不存在的字典树的状态链接到了失配指针的对应状态。在原字典树中，每一个结点代表一个字符串 S，是某个模式串的前缀。而在修改字典树结构后，尽管增加了许多转移关系，但结点（状态）所代表的字符串是不变的。

而 trans[S][c] 相当于是在 S 后添加一个字符 c 变成另一个状态 S’。如果 S’ 存在，说明存在一个模式串的前缀是 S’，否则我们让 trans[S][c] 指向 trans[fail[S]][c]。由于 fail[S] 对应的字符串是 S 的后缀，因此 trans[fail[S]][c] 对应的字符串也是 S’ 的后缀。

换言之在 Trie 上跳转的时侯，我们只会从 S 跳转到 S’，相当于匹配了一个 S’；但在 AC 自动机上跳转的时侯，我们会从 S 跳转到 S’ 的后缀，也就是说我们匹配一个字符 c，然后舍弃 S 的部分前缀。舍弃前缀显然是能匹配的。那么 fail 指针呢？它也是在舍弃前缀啊！试想一下，如果文本串能匹配 S，显然它也能匹配 S 的后缀。所谓的 fail 指针其实就是 S 的一个后缀集合。

tr 数组还有另一种比较简单的理解方式：如果在位置 $u$ 失配，我们会跳转到 fail[u] 的位置。所以我们可能沿着 fail 数组跳转多次才能来到下一个能匹配的位置。所以我们可以用 tr 数组直接记录记录下一个能匹配的位置，这样就能节省下很多时间。

这样修改字典树的结构，使得匹配转移更加完善。同时它将 fail 指针跳转的路径做了压缩（就像并查集的路径压缩），使得本来需要跳很多次 fail 指针变成跳一次。

多模式匹配

int query(char* t)
{
	int u = 0, res = 0;
	for (int i = 1; t[i]; i++)
	{
		u = tr[u][t[i] - 'a'];  // 转移
		for (int j = u; j && e[j] != -1; j = fail[j])
		{
			res += e[j], e[j] = -1;
		}
	}
	return res;
}

这里 $u$ 作为字典树上当前匹配到的结点，res 即返回的答案。循环遍历匹配串，$u$ 在字典树上跟踪当前字符。利用 fail 指针找出所有匹配的模式串，累加到答案中。然后清零。在上文中我们分析过，字典树的结构其实就是一个 trans 函数，而构建好这个函数后，在匹配字符串的过程中，我们会舍弃部分前缀达到最低限度的匹配。fail 指针则指向了更多的匹配状态。