字符串算法三连击

在讲AC自动机之前我们先来看一下Trie树

Trie 树

Trie树可以用于查找一组字符串的前缀

图示:

Trie

最大异或和

给出 个数 ，求

思路

把每个数看成是一个 长度的二进制串，最高位是第一个字符，对这些二进制串构造一个 Trie 树， Trie 树上记录子树内一共有多少个数

考虑查询这个集合中的数与 异或的最大值，从最高位开始考虑，如果有这一位不同的就应该选择不同的那个分支。这样按照Trie 树走下去，就可以查找出来与 x 异或能得到的最大值

对于 到 每一个都这样做一次，就得到了最大值。时间复杂度

First

给 n 个字符串。现在你可以指定 26 个字母的大小顺序，问哪些
字符串可能在指定顺序后变成字典序第一的串。

思路

首先对所有字符串构造一个 Trie 树

考虑某个字符串能否是字典序最小的。如果这个字符串某个字符 在 Trie 树上有同层同父亲的边，这条边上字母为 ，就说明这会成为一个限制，要求字符 在新的大小顺序中必须小于字符

把所有 小于 的限制在图中连一条 到 的有向边，如果这个图可以拓扑排序，则这个串可以是字典序最小的串。然后对所有字符串都进行判断就可以了

自动机

自动机的五个组成要素：

  • 状态集合
  • 初始状态 ，只能有一个
  • 接收状态集合，可以有多个
  • 字母表
  • 转移函数 :

上述只是严格的数学形式，然而像我这种大蒟蒻当然是看不懂的，就只能直接看AC自动机了

AC自动机

在KMP算法中，匹配单个字符的时候，我们只需要按照文本线性的扫一遍，然后中途失配的时候，next数组会引导k回溯到正确的位置进行下一步的匹配。

但是多个模式串的时候要怎么匹配呢？Trie树不就是一个多模式的匹配吗，如果我们将KMP和Trie数结合起来，是不是会有意想不到的效果呢？

有了这些思考，AC自动机算法就这样产生了。

在AC自动机中，我们首先将每一个模式串插入到Trie树中去，建立一棵Trie树，然后构建fail指针，fail指针，顾名思义，就是当匹配失败的时候，用来引导k回溯的一个插穿在Trie树的各个节点之间的一些指针，就和KMP算法中的next数组是一样的道理。

将所有的字符串构建成一个 Trie 树，按照 BFS 的顺序遍历每个节点，对每个 Trie 树上的节点维护一个 fail 指针

对于每个节点，如果它有第 个儿子，设为 ，则顺着当前节点的 fail 指针向上跳。如果跳到的节点有第 个儿子，设为 ，则 的 fail 指针指向

AC

(图不好见谅

虚线为 fail 指针，可以看出与 KMP 的 next 数组相似的 “前缀等于后缀” 的关系

在AC自动机上匹配

在AC自动机上匹配,相当于在 Trie 树上匹配，顺着 Trie 树走就可以了。如果某次匹配是失败的，则顺着 fail 指针跳回去，直到匹配成功或者 fail 指针跳到根也没有成功。

AC 自动机上每一个节点对应匹配的一种 状态，只要我们知道当前走到了 AC 自动机上的哪个节点，无需知道字符串已经匹配的内容就可以继续匹配。利用这点性质可以在这些状态上做递推等

AC自动机与其他自动机的区别

AC 自动机的带有 fail 指针的形式还不符合自动机的一般描述，试着把它写成一个自动机的形式。

在 AC 自动机的状态 上，想象下一个需要匹配的字符是 ，需要顺着 fail 指针跳到一个有儿子 节点的位置。如果一直找不到，那么下一个状态应该是 Trie 树的根。

注意到这个转移只跟当前状态和下一个需要匹配的字符有关，这正是一般自动机的转移函数 : 用这种方式思考递推问题会更容易

KMP自动机

KMP 算法就是 AC 自动机算法在单个字符串上的情形，但是因为不需要枚举字符集，所以复杂度是 而不是 。

一个串对应的 AC 自动机就是 KMP 自动机， KMP 过程相当于在 KMP 自动机上做匹配。 KMP 的 next 数相当于 AC 自动机的 fail 指针

应用

HNOI 2008 GT 考试

给定一个数字串
求不出现 的 位数字串有多少个

题解

很大，考虑矩阵乘法。矩阵乘法本质是递推，递推的状态是什么？

对 构造 AC 自动机，它上面的状态可以描述匹配的进度。f[i][j] 表示 i 位数字串中，在 AC 自动机上匹配状态为 j 的串有多少个。这里对自动机做一点小改造，如果一个串已经匹配成功了，那么不论后续出现什么数字它都已经不应该被记入答案了，所以把 AC 自动机的接受态上的所有转移都连到自己。

第二维状态只有最多 个，且对于第一维来说这是一个线性递推，利用矩阵乘法优化，复杂度可以做到

NOI 2011 阿狸的打字机

有一个打字机，有三种操作

  1. 输入一个字母
  2. 删除最后一个输入的字母
  3. 打印当前字符串

一共进行了 次操作，有 个询问，每次询问第 个打印的字符串在第 个打印的字符串中出现多少次。

题解

前两个操作相当于构造了一棵 trie 树，对这个 trie 树构造一个AC 自动机。串 是串 的子串等价于串 是串 一个前缀的后缀

考虑在 Trie 树上询问节点 对应串在节点 对应串中出现了几次。从节点 出发，顺着 fail 指针走，如果能到达节点 ，说明 是 的后缀

所以只需要看从根节点到 的路径上，有多少个节点可以沿着fail 指针走到

构造 fail 树（这棵树上 的父亲就是 的 fail 指针），离线处理后相当于这棵树上单点修改子树求和，用树状数组解决