AC 自动机

AC 自动机

​ 真正的字符串旅途已走上正轨

思想

​ 大家一定都学过了 KMP 匹配算法和字典树了吧

​ 为没有学习过的同学附上链接：Exqule's Blog KMP-匹配算法，Exqule's Blog Trie-字典树。

​ 我们所使用的 $KMP$ 算法是对于单个模式串匹配的高效算法，但是如果出现了多个模式串，如果直接暴力对所有的模式串跑 $KMP$ 算法势必不是最优秀的。

​ 考虑到 $KMP$ 算法的真正思想其实在于构造 $next$ 数组，而避免不必要的操作。

​ 那么，考虑到多个模式串放在一起的最优结构并非是链状，而恰好是一棵字典树。

​ 那么只需要把字典树上的作为后缀的叶子结点和前缀末尾的结点相连，而实现树上 $KMP$ 算法。

​ 总而言之，$KMP$ 匹配算法和 $Trie$ 字典树的联动，就是 $AC$ 自动机的核心思想。

实现

​ 实现步骤主要分为两大部分：树上 $next$ 的构造，树上调用 $next$ 本身。

​ 而这里，$next$ 本是已经不是线性结构，那么我们又称之为 $fail$ 指针，即失配指针。

fail 失配指针的构造

​ 考虑 $bfs$ 对于每一个结点的构造失配指针，首先将每个模式串的首字母加入队列中。

​ 每次通过对字符集大小进行查询其子结点，如果有就进行连边，再递归向下知道没有时回溯。

​ 但是考虑到形同 $KMP$ 匹配算法中使用 $while$ 语句递归会产生大量冗余的操作。

​ 我么考虑对于存在的子结点直接从子结点连边到 $fail$ 指针下的相同结点，并加入到队列中。

​ 如果不存在子结点，则考虑直接优化路径，从结点本身连边到 $fail$ 指针下的相同子结点。

​ 放入代码方便理解：

while(Head<Tail)
{
	int dep=q[Head++];
	for(int i=0;i<26;i++)
	{
		if(trie[dep][i])
		{
			fail[trie[dep][i]]=trie[fail[dep]][i];
			q[Tail++]=trie[dep][i];
		}
		else trie[dep][i]=trie[fail[dep]][i];
	}
}

调用 fail 指针匹配

​ 由于 $fail$ 指针的构造完成，形成自动机，那么我们可以直接通过子结点的迭代实现转移。

​ 然后对于题目要求计入答案，输出即可，附上代码：

for(int i=0,dep;i<s.length();i++)
{
	dep=trie[dep][s[i]-'a'];
	while(tmp[dep]!=-1 && dep)
	{
		ans+=tmp[dep];
		tmp[dep]=-1;
	}
}

​ 上述为 洛谷题库-P3808 【模板】AC自动机（简单版） 的代码。