AC 自动机

AC 自动机用于解决多模匹配问题。

P3808 【模板】AC 自动机（简单版）

询问所有模式串在文本串中出现的总次数。

自动机上节点记录 word 表示此处为结尾的单词数。

// 名字空间封装好的 AC 自动机
namespace AC
{
	int tr[maxn][26], tot;
	int word[maxn], fail[maxn];
	/*
	失配指针 fail：
	当前节点所表示字符串的最长真后缀，使得该后缀作为某个单词的前缀出现
	也可以理解为：当前状态指向后缀不变的最长字符串的指针
	还可以理解为：当前状态删掉最少的前缀到达的字符串的指针
	*/
	void insert(char *s) // 就正常插入
	{
		int u = 0;
		for (int i = 1; s[i]; i++)
		{
			int c = s[i] - 'a';
			if (!tr[u][c])
				tr[u][c] = ++tot; // 如果没有则插入新节点
			u = tr[u][c];		   // 搜索下一个节点
		}
		word[u]++; // 尾为节点 u 的串的个数
	}

	void build()
	{
		queue<int> q;
		for (int i = 0; i < 26; i++) // 将深度为 2 的字符插入队列
			if (tr[0][i])
				q.push(tr[0][i]);
		while (q.size()) // bfs
		{
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++)
			{
				int v = tr[u][i]; // 每个循环都是求出其儿子的 fail
				if (v)			  // 若该儿子是真实的
				{
					fail[v] = tr[fail[u]][i]; // 儿子的 fail 指向父亲的 fail 的同类儿子
											  // 另一种版本：我的前世和我父亲的前世在一起
					q.push(v);
					//*********非常容易忘！**********
				}
				else
					tr[u][i] = tr[fail[u]][i]; // 否则儿子直接定义为父亲的 fail 的同类儿子
											   // 我是假的，那就跟我父亲的前世走吧

				/*
				解释：
				虚点没有 fail，其本身就代表了跳 fail 的最终结果
				对每一个虚点，其记录了层数最小的实点，且它跟着父亲走
				*/
			}
		}
	}

	int query(char *t)
	{
		int u = 0, res = 0;
		for (int i = 1; t[i]; i++)
		{
			u = tr[u][t[i] - 'a']; // 向下走一层（是虚点则回溯）
								   // 这一行就干了朴素 ACAM 跳 fail 一大堆干的事情

			for (int j = u; j && word[j] != -1; j = fail[j]) // 不断跳 fail
			{
				res += word[j]; // 路径上的所有状态都在文本串中出现了，注意每个点可能有多个单词
				word[j] = -1;	// 每个单词只能统计一遍

				/*
				word[j]==-1 说明这个单词已经被统计过了，其后的单词也在那一遍遍历中统计过了，因此可以跳出
				一次跳 fail 的过程中保证了一部分后缀不变，跳 fail 的实质就是删掉部分前缀
				*/
			}
		}
		return res;
	}
}

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

找到出现次数最多的单词及其出现次数（可能不止一个）。

记录 word 同前例，取最大值即可，在节点上可以记录初始字符串的序号。最后把同次数的所有单词输出。

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

好戏登场。

照理说正常求 cnt 输出即可，但 query 的跳 fail 太慢了。

void query(char *t)
{
	int u = 0;
	for (int i = 1; t[i]; i++)
	{
		u = tr[u][t[i] - 'a'];
		for (int j = u; j; j = fail[j])
			val[j]++;
	}
	for (int i = 0; i <= tot; i++)
	{
		for (int j : idx[i])
			cnt[j] = val[i];
	}
}

这时我们就要祭出拓扑排序优化啦 (￣▽￣)／

注意到每次跳 fail 其实是做一个类似于前缀和的操作，那我们就可以预先操作先访问到的节点，最后一并求和，那么效率就会优化。

int in[maxn]; // 入度
int tp[maxn], tt;
void topsort()
{
	for (int i = 1; i <= tot; i++) in[fail[i]]++;
	queue<int> q;
	for (int i = 0; i <= tot; i++)
		if (!in[i]) q.push(i);
	while (!q.empty())
	{
		int u = q.front(), v = fail[u];
		q.pop();
		tp[++tt] = u;
		in[v]--;
		if (!in[v]) q.push(v);
	}
}
void query(char *t)
{
	int u = 0;
	for (int i = 1; t[i]; i++)
	{
		u = tr[u][t[i] - 'a'];
		val[u]++;
	}
	for (int i = 1; i <= tt; i++)
	{
		int x = tp[i];
		val[fail[x]] += val[x];
	}
	for (int i = 0; i <= tot; i++)
	{
		for (int j : idx[i])
			cnt[j] = val[i];
	}
}

P5829 【模板】失配树

求字符串长度为 \(x\) 的前缀和长度为 \(y\) 的前缀的最长公共 border。

border：公共前后缀。

这是一道番外题，但与上例的思想共通。

首先肯定是要 KMP，求出 nxt 即为该前缀的 border。

一种朴素的做法是每次跳 \(nxt[i] \leftarrow nxt[nxt[i]]}\)，但这样显然会被卡。

发现 nxt 在迭代的过程中单调递减，且最终会跳到 \(0\)，这样则构成一条链结构。

两条链结构在交叉后不会再分开，符合树形结构。于是我们把 nxt 构成一棵树，答案就是 lca。

这与 AC 自动机有什么关系呢？注意看 fail 数组的构建过程，也同样符合该特征，这说明 fail 也同样构成一棵树。这带来很多有趣的性质。

P3966 [TJOI2013] 单词

板子题。求出 cnt 数组输出，记得拓扑优化建图。

P3121 [USACO15FEB] Censoring G

我们已经讨论过只有一个模式串的情况，现在看看多个单词怎么做。

一个模式串是栈 + KMP，多个模式串自然想到栈 + AC 自动机，匹配成功的时候弹出等同于模式串长个字符，并把 \(u\) 还原到新的栈顶的匹配位置。

理清思路代码才好写。