AC 自动机学习笔记

给定 $n$ 个模式串 $t_i$ 和一个文本串 $s$ ，求出 $s$ 中有多少个 $t_i$ 出现了。

考虑先将所有模式串插入到一棵 Trie 树中，然后在上面跑（不停从点 $u$ 走到 $u$ 的边权为 $s_i$ 的儿子，即令 $u$ 变为 $son_{u,s_i}$ ）。这样若当前点 $u$ 为某个 $t_i$ 对应的点（可以在插入时给这个点打标记），则说明 $t_i$ 在 $s$ 中出现了。

但是这样不停跑可能会出现这样的情况：当前位于点 $u$ ，而 $son_{u,s_i}=0$ 即不存在对应的儿子，此时我们无法直接走到 $son_{u,s_i}$ 。不妨称这种情况为“失配”。

解决办法很简单，假设第一次出现这种情况时跑完了 $s_{[1,i]}$ ，当前在点 $u$ 且 $son_{u,s_{i+1}}=0$ 。则此时 $u$ 对应的字符串是 $s_{[1,i]}$ 。为了能继续往下跑，我们可以跳到一个 Trie 树上的节点 $v$ ，使得 $v$ 代表的字符串是 $s_{[1,i]}$ 的后缀，且 $v\not=u$ ：

如果这样的 $v$ 有很多个，那么跳到最深（代表的字符串最长）的那个一定是最优的（因为从它出发能跳到其它合法的 $v$ ）。并且由于 Trie 中每个点的字符串两两不同，故最深的 $v$ 一定只有一个。

不妨令 $fail_u$ 为最深的这样的 $v$ ，即对应字符串是点 $u$ 对应字符串的后缀且深度最大的点 $v$ （需满足 $v\not=u$ ）。

考虑 $fail$ 的求解。注意到 $fail_u$ 的深度一定小于 $u$ 的深度，故可以使用 bfs 求解。先将 $fail_0$ 以及所有 $0$ 的儿子的 $fail$ 设为 $0$ 。对于一个点 $u$ 及 $v=son_{u,i}\not=0$ ：

令 $p=fail_u$ $p = f a i l_{u}$ 并不断令 $p=fail_p$ $p = f a i l_{p}$ ，直到：
- $p=0$ ，则令 $fail_v=0$ ；
- $son_{p,i}\not=0$ ，则令 $fail_v=son_{p,i}$ ；

暴力跳太慢了，不妨在 $son_{u,i}=0$ 时令 $son_{u,i}=son_{fail_u,i}$ ，这样就不用暴力跳了：

若 $son_{u,i}\not=0$ ，则令 $fail_{son_{u,i}}=son_{fail_u,i}$ ；

即 $son_{u,i}$ 实际上变成了：

从 $u$ 出发，不断令 $u=fail_u$ 直到边权为 $i$ 的儿子 $v$ 存在， $son_{u,i}$ 就为这个 $v$ ；

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

inline void build()
{
	queue<int> q; 
	fail[0]=0;
	for(int i=0;i<26;i++)
	{
		int v=son[0][i];
		if(v!=0) fail[v]=0,q.push(v);
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int v=son[u][i];
			if(v!=0) fail[v]=son[fail[u]][i],q.push(v);
			else son[u][i]=son[fail[u]][i];
		}
	}
}

对于例题，不难发现当在点 $u$ 时，实际上能匹配 $u,fail_u,fail_{fail_u},\dots$ 对应的字符串，即不断跳 $fail$ 经过的点都能匹配到。故还需记录一个点是否被跳过了，如果经过跳过的点就停止跳 $fail$ ：

inline int calc(char* s,int n) // sum[u] 表示有多少个文本串等于 u 表示的字符串
{
	int u=0,res=0;
	for(int i=1;i<=n;i++)
	{
		int id=s[i]-'a'; 
		u=son[u][id];
		int v=u;
		while(v!=0&&sum[v]!=-1) // 跳到根节点或者跳到过就不用跳 
		{
			res+=sum[v]; // 计算贡献 
			sum[v]=-1;   // 标记跳到过了 
			v=fail[v];   // 继续跳 fail 
		}
	}
	return res;
}

实际上，由于每个点只有一个 $fail$ ，且不断跳 $fail$ 必定停留在点 $0$ ，故 $fail$ 实际上是一棵根为 $0$ ，包含所有 Trie 中节点的树，即 fail 树。

练习：

AC 自动机学习笔记

感谢您的支持，我会继续努力的!