AC 自动机学习笔记

AC 自动机是一种字符串匹配算法，而不是自动让你 AC 的作弊工具……（说实话我也不知道为什么它叫 AC 自动机）

它主要是解决这一类问题：给定 $n$ 个模式串 $t_i$ 和一个文本串 $s$，让 $s$ 和这 $n$ 个 $t$ 做匹配。

例如这道模板题，就是要求文本串里有多少个模式串出现了。

考虑对于这种有多个模式串的匹配问题。我们可以先对于所有模式串建一棵 trie 树，然后在 trie 上跑匹配。

注意到在任意时刻，如果我们匹配到了节点 $u$，那么我们可以跳到所有表示的字符串是 $u$ 所表示的字符串的后缀的节点 $v$。

而为了不重不漏，我们肯定要跳到表示字符串长度最长的那一个点，因为从那个点继续跳就可以访问完所有表示的字符串是 $u$ 所表示的字符串的节点了。

可以用一个数组来存这个东西，令 $fail_u$ 存表示的字符串是 $u$ 的一个后缀且最长的节点 $v$。

先考虑 $fail$ 数组的求解，由于 $fail_u$ 的深度肯定小于 $u$ 的深度，所以我们可以使用 bfs 来求解。很明显，$fail_1=1$，对于所有节点 $1$ 的儿子 $v$，$fail_v=1$。对于一个节点 $u$ 的儿子 $v$，设 $(u,v)$ 的边权为 $i$，那么 $fail_v=son_{fail_u,i}$。

在求解 $fail$ 数组时，我们要顺便把 $u$ 的所有边权为 $i$ 且不存在的儿子 $v$ 赋值为 $son_{fail_u,i}$。这是为了令匹配的时候如果没有儿子可以不用暴力跳 $fail$，可以 $O(1)$ 重新开始匹配。

求 $fail$ 数组的代码如下：

inline void init() // 求解 fail 数组 
{
	queue<int> q; // bfs 用的队列 
	fail[1]=1; // fail[1] = 1
	for(int i=0;i<26;i++)
	{
		int v=son[1][i];
		if(v!=0) // 有这个儿子，fail 设置为 1 + 入队 
		{
			fail[v]=1;
			q.push(v);
		}
		else // 没有这个儿子，造一个！ 
		{
			son[1][i]=1;
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		int fiu=fail[u]; // 父亲的 fail 
		for(int i=0;i<26;i++)
		{
			int v=son[u][i];
			if(v!=0) // 有这个儿子，设置 fail  + 入队 
			{
				fail[v]=son[fiu][i];
				q.push(v);
			}
			else // 没有这个儿子，造一个！ 
			{
				son[u][i]=son[fiu][i];
			}
		}
	}
}

有了 $fail$ 数组，匹配也很简单了：

inline int slove() // 匹配 
{
	int u=1,res=0;
	int len=strlen(str+1); // str 是一个全局变量，调用 slove() 时存的是文本串 
	for(int i=1;i<=len;i++)
	{
		int id=str[i]-'a'; 
		u=son[u][id]; // 在 trie 树（trie 图？）上继续走一步 
		int tmp=u;
		// 计算当前能匹配到的所有字符串对答案的贡献
		while(tmp!=1&&sum[tmp]!=-1) // 跳到根节点或者跳到过就不用跳 
		{
			res+=sum[tmp]; // 计算贡献 
			sum[tmp]=-1; // 标记跳到过了 
			tmp=fail[tmp]; // 继续跳 fail 
		}
	}
	return res;
}

这道题就做完啦，给出完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

int n;
char str[1000005];
int cnt,son[1000005][26];
int fail[1000005],sum[1000005];

inline void ins()
{
	int u=1;
	int len=strlen(str+1);
	for(int i=1;i<=len;i++)
	{
		int id=str[i]-'a';
		if(son[u][id]==0)
		{
			son[u][id]=++cnt;
		}
		u=son[u][id];
	}
	sum[u]++;
}

inline void init() // 求解 fail 数组 
{
	queue<int> q; // bfs 用的队列 
	fail[1]=1; // fail[1] = 1
	for(int i=0;i<26;i++)
	{
		int v=son[1][i];
		if(v!=0) // 有这个儿子，fail 设置为 1 + 入队 
		{
			fail[v]=1;
			q.push(v);
		}
		else // 没有这个儿子，造一个！ 
		{
			son[1][i]=1;
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		int fiu=fail[u]; // 父亲的 fail 
		for(int i=0;i<26;i++)
		{
			int v=son[u][i];
			if(v!=0) // 有这个儿子，设置 fail  + 入队 
			{
				fail[v]=son[fiu][i];
				q.push(v);
			}
			else // 没有这个儿子，造一个！ 
			{
				son[u][i]=son[fiu][i];
			}
		}
	}
}

inline int slove() // 匹配 
{
	int u=1,res=0;
	int len=strlen(str+1); // str 是一个全局变量，调用 slove() 时存的是文本串 
	for(int i=1;i<=len;i++)
	{
		int id=str[i]-'a'; 
		u=son[u][id]; // 在 trie 树（trie 图？）上继续走一步 
		int tmp=u;
		// 计算当前能匹配到的所有字符串对答案的贡献
		while(tmp!=1&&sum[tmp]!=-1) // 跳到根节点或者跳到过就不用跳 
		{
			res+=sum[tmp]; // 计算贡献 
			sum[tmp]=-1; // 标记跳到过了 
			tmp=fail[tmp]; // 继续跳 fail 
		}
	}
	return res;
}

int main()
{
	scanf("%d",&n);
	cnt=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		ins();
	}
	init();
	scanf("%s",str+1);
	printf("%d\n",slove());
	return 0;
}

练习题目：

P3796 【模板】AC自动机（加强版）

P5357 【模板】AC自动机（二次加强版）

P5231 [JSOI2012]玄武密码

P3966 [TJOI2013]单词

P2322 [HNOI2006]最短母串问题

P3121 [USACO15FEB]Censoring G

P2444 [POI2000]病毒