给宝宝的AC自动机启蒙指南（宝宝的第一本）

AC自动机

根据已有经验，学完虚数会变虚，然后写出的代码就不是人能看的了

所以我们来学实树罢（喜）

以上为废话博客背景

有限状态自动机

首先我们来了解一下自动机是啥。

说的通俗一点，我们可以把自动机看成一张有向图，有一个点在起始节点。每当你输入一个合法的东西，这个点就会按照一定规则在边上移动。也就是说，你输入一些东西，这个点就会移动到一个确定的地方是不是很自动呢

我们接触到的第一个自动机其实不是AC自动机，而是trie树。大家可以看一看trie树是不是符合上面这些要求。

当然我是认为这个最大的用处在于让学习AC自动机的人明白trie树很重要。啥？trie树上跑KMP？AC自动机的数组可比KMP好懂多了。相信我。

引入

当然我们是可以按照自动机的结构来讲解的。但那样宝宝就看不懂了。

现在有这样一个问题：有很多模式串和一个文本串，要求有几个模式串在文本串中出现过。

显然，我们可以用模式串建出一棵trie树，一个字母一个字母的跑，跑不到了就重头再来。

但是这很费时间！如果我们能在树上找到失配字符串的后缀，那么失配以后，我们可以直接跳到树上的后缀继续匹配的！：

这是因为，尽管失配了，但我们仍能匹配她的后缀，无需再次重头开始。

AC自动机就是干这个的。

AC自动机的构造

AC自动机，实现的实际上就是多模式串的匹配。我们把这些模式串建成一棵trie树，这是引入里面提到的操作。

我认为，

接下来，我们设数组fail[u]为当在点u失配时可以跳到哪个点接着匹配。

我们肯定希望跳到的点所匹配的长度越大越好，所以我们规定fail[u]为u在trie树中的最长后缀所在节点。

我们来讨论一下怎么求fail。首先显然，与trie树虚拟根节点（这里我设为0）相连的边的fail肯定是0。然后我们根据一个点u的fail去推儿子ch[u][i]的fail，这样的好处是不用记录父亲。

为了表示方便，我们把ch[u][i]设为v

但首先，我们需要判断v存不存在。

v存在，此时如果fail[u]也存在连向相同字符的边，那么我们就把fail[v]赋值为ch[fail[u]][i]（最长后缀和字符串同步加一还是最长后缀）。如果不存在，那我们就需要找到fail[u]的fail，再进行一次判断，因为此时她是有可能存在的最长后缀了。如果还不存在，我们还有再来一次，直到存在或到0。。。好麻烦诶

别担心，我们之后会让这个步骤变得简单。现在我们来看第二种情况：v不存在。此时我们不需要更新v的fail节点，但我们可以想一个问题：当v不存在时，之后跳到u，想连到v，发现v不存在后，还得向上跳。那么，我们为什么不直接把v赋值成上面的某个有这条边的节点or0呢？

我们优化完的策略如下：如果v不存在，那么我们将ch[u][i]设为ch[fail[u]][i]，如果存在，不动ch数组，将fail[v]赋值为ch[fail[u]][i]。

为什么这样能达到同样的效果呢？当v存在时，之后连向u的节点，都会把ch赋值为v，直到有另一个更大的后缀存在。当v不存在时，会向fail连，最终会连到上一个存在的节点，或者直接连到0。

大家可以画个图理解成一下，最终会产生这种状况:

ch[u][i] = ch[fail[u]][i] = ch[fail[fail[u]]][i] = ... = w, ch[fail[w]][i] = ch[fail[fail[w]]][i] = ... = 0

上面这种情况不一定准确啊。。。只是想让大家理解一下如果不存在，会直接跳到上一个存在这条边的节点。

或者，如果你的脑回路与我相近，可以尝试思考这个与并查集路径压缩之间的联系。。。

这样子我们就可以直接fail[v]=ch[fail[u]][i]了。因为就算fail[u]并没有这条边，ch[fail[u]][i]也被赋为了最近的一个有这条边的节点。如果都没有，就会干脆赋为0。

由于我们要一层一层的求fail数组，所以我们采用BFS

void build()

{

	queue<int> q;

	for(int i = 0;i < 26;i ++) if(ch[0][i]) q.push(ch[0][i]);

	while(!q.empty())

	{

		int u = q.front();

		q.pop();

		for(int i = 0;i < 26;i ++)

		{

			if(!ch[u][i]) ch[u][i] = ch[fail[u]][i];

			else fail[ch[u][i]] = ch[fail[u]][i],q.push(ch[u][i]);//只有存在才能进队

		}

	}

}

这样还有一个好处，就是我们查询时不需要fail数组了，直接按照trie树的方法查询就行。如果失配就会自动跳到最长的能配对的位置。

AC自动机的查询

这个依题目而定，我们来看几道题目吧

AC自动机模板

给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\)，求有多少个不同的模式串在文本串里出现过。

两个模式串不同当且仅当他们编号不同。

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^6\)，\(1 \leq |t| \leq 10^6\)，\(1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6\)。\(s_i, t\) 中仅包含小写字母。

这个是洛谷上面的模板题。

我们根据fail的定义发现，如果我们更新了一个点，即使她的fail不会被走到，也会作为她的后缀存在于文本串中。也要进行更新。

于是我们搞个标记数组，按照trie树的匹配，每匹配到一个点就跳她的fail，一路跳到vis为1即可

注意这里只是统计出现过，所以我们可以标记到过的点，被标记的点就不再统计



int tiao(string s)

{

	int n = s.size(), u = 0, ans = 0;

	for(int i = 0;i < n;i ++)

	{

		int p = s[i] - 'a';

		u = ch[u][p];

		for(int j = u;j && !ton[j];j = fail[j]) ans += col[j], ton[j] = 1;

		// 当一个点被标记过，他的所有的后缀肯定也被标记过，就不用继续跳了

	}

	return ans;

}

更nb的AC自动机模板

题目描述

有 \(N\) 个由小写字母组成的模式串以及一个文本串 \(T\)。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 \(T\) 中出现的次数最多。

输入格式

输入含多组数据。保证输入数据不超过 \(50\) 组。

每组数据的第一行为一个正整数 \(N\)，表示共有 \(N\) 个模式串，\(1 \leq N \leq 150\)。

接下去 \(N\) 行，每行一个长度小于等于 \(70\) 的模式串。下一行是一个长度小于等于 \(10^6\) 的文本串 \(T\)。保证不存在两个相同的模式串。

输入结束标志为 \(N=0\)。

这道题在洛谷上叫做AC自动机加强版，之后还会有个二次加强版

看起来是让我们求哪些串出现的最多，实际上就是求每个串出现的次数。

于是我们想，我们更新一个节点，她的所有后缀也会被更新。

然后我们把vis扔了，然后跳到一个串，就跳她的fail，一路更新。

看起来很不对，但实际上，每次fail最少也会使深度减少1，所以稍微算算就知道能过

最nb的AC自动机模板

就是上面那题加了数据范围

我们想，我们做第一个模板时，有vis，所以能过，但第二个模板时我们把vis扔了，所以就过不了了

但实际上我们可以从另一个角度优化，第二个模板每一次跳fail都会跳到很多重复的节点，每次+1+1太麻烦，我们攒到最后一起加就行了

AC自动机的应用

AC自动机优化DP

都是套路，如果不是套路，就是套路套套路。

设dp[i]为遍历到AC自动机上节点i时blabla的答案，有时也许要加个限制条件。然后外面套一层循环，里面从节点转移儿子就行

AC自动机的奇怪题目

[POI2000]病毒

题目描述

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果 \(\{011, 11, 00000\}\) 为病毒代码段，那么一个可能的无限长安全代码就是 \(010101 \ldots\)。如果 \(\{01, 11, 000000\}\) 为病毒代码段，那么就不存在一个无限长的安全代码。

现在给出所有的病毒代码段，判断是否存在无限长的安全代码。

输入格式

第一行包括一个整数 \(n\)，表示病毒代码段的数目。

以下的 \(n\) 行每一行都包括一个非空的 \(01\) 字符串，代表一个病毒代码段。

输出格式

如果存在无限长的安全代码，输出 TAK，否则输出 NIE。

之前的题目都是要匹配，这道题是不能匹配。而且只要她的fail不合法，她也就不合法

如果走到了走过的地方还没有到非法节点，那么就输出TAK

巴特西

给宝宝的AC自动机启蒙指南（宝宝的第一本）

有限状态自动机

引入

AC自动机的构造

AC自动机模板

更nb的AC自动机模板

题目描述

输入格式

最nb的AC自动机模板

AC自动机的应用

AC自动机优化DP

AC自动机的奇怪题目

[POI2000]病毒

题目描述

输入格式

输出格式

最新文章

热门文章