1. 哈希

1.1. 简介

哈希是一种将字符与数字映射的算法，比较基础，但自己学的不是很好，应用不来。

1.2. 方法

一般选用一个 $base$ 和 一个 $mod$。$base$ 没什么限制，$mod$ 需要尽量大（至少大于长度）以及必须是质数。

1.3. 例题

P7469 [NOI Online 2021 提高组] 积木小赛

题意：

给出两个长度为 $n$ 的字符串 $a$ 和 $b$，求 $a$ 的子序列和 $b$ 的字串有多少种情况会相同。

思路：

判断相同就可以用哈希来做了，将字符转化为数字。因为 $b$ 的要求更严格，因此我们可以枚举 $b$ 的字串，枚举一个在 $a$ 中的指针 $pos$ 判断是否还相同，是的话存下哈希值，最后去重后的个数就是答案。

2. KMP

2.1. 简介

kmp 是一种用来进行字符串匹配的算法，核心思想是通过记录前后缀最大公共长度来优化转移过程。这在网上介绍太多了。

2.2. 作用

1. 求单个模式串 $t$ 在文本串 $s$ 中出现位置。

2. 求循环节（广义或狭义）。

2.3. 例题

CF1200E Compress Words

题意：

给出 $n$ 个字符串，将相邻的两个字符串合并，即将最长公共前后缀合在一起，求最后的字符串。

思路：

看到最长公共前后缀想到 $kmp$，直接将答案和当前串拼在一起再求 $kmp$ 即可，不过我们发现可能时间会被卡，同时我们发现合并最多合并两个长度的最小值，因此我们取 $\min(len_{ans},len_{now})$ 即可。同时为了避免出现长度大于字符串的情况，因此多加一个奇怪的字符隔开。

CF808G Anthem of Berland

题意：

给出字符串 $s$ 和 $t$，$s$ 中含有问号，问号可以当作任意字符。问所有情况下在 $s$ 中匹配 $t$ 最多的次数。

思路：

题目范围 $|s| \times |t| \leq 10^7$，这不是明示我们用 $O(nm)$ 的算法吗？显然枚举 $s$ 的每一位就有 $O(n)$，而我们又可以 $O(m)$ 暴力枚举判断每一位是否可以匹配。那么我们有了初步的想法：设 $f_i$ 表示前 $i$ 个字符最多匹配的次数，那么若当前能匹配的话，$f_i = f_{i-m} + 1$。

但是这样显然是不行的，因为没有考虑当前的前缀和前面已经匹配的 $t$ 的后缀合起来的情况。看到前后缀就想到 kmp，我们可以通过跳转 $nxt$ 数组来保证当前前缀和 $t$ 的后缀相同。因此我们再设一个 $g_i$，表示前 $i$ 个字符，且最后为一个 $t$ 的最大匹配数。那么若 $i$ 可以匹配，那么有转移

$g_i=\max_{j=nxt_m}^{j=nxt_j}(g_{i - (m-j)} + 1,g_i)$

最后每个 $f_i=\max(f_i,g_i)$。

SP263 PERIOD - Period

题意：

对于字符串 $s$ 所有前缀，若其存在狭义循环节，则输出前缀长度和最大循环次数。

思路：

首先对于广义循环节我们之前已经做过了：最短循环节长度为 $n-nxt_n$，证明非常巧妙，将前缀和后缀分别单独拿出来，画个图很好理解。本题要求的是狭义循环节，其实也一样的，不过要求字符串长度是循环节长度的倍数。

UVA1328 Period

上题的双倍经验。

P2375 [NOI2014] 动物园

题意：

给一个长度为 $n$ 的字符串 $s$，求出到 $s_i$ 的满足不重叠的公共前后缀个数。

思路：

是个 kmp 的好题。增加了我对 kmp 的理解。其实自己差不多都想到了，但就差那么一步啊……手玩一下有个思路：先求出 nxt 数组，然后对于每一位都去跳它的 nxt 数组，若满足 $nxt < i - nxt + 1$ 的话答案加 $1$，这样时间复杂度太大，只能得 $50$ 分。思考问题的本质，每一个 $i$ 对答案的贡献就是满足上面条件的 nxt 个数，而就在这里我没想清楚，乱写了错误的东西。其实非常简单，先递推求出每一位的 nxt 的个数（这里也想到了），然后就像求 nxt 一样，枚举一个指针 $j$，保证其满足 kmp 和上面的条件，然后更新答案即可。

3. AC 自动机

OI-Wiki

3.1. 简介

AC 自动机是一种用来进行多模式串匹配的算法，其实就是在 trie 上进行 kmp。

简单来说，建立一个 AC 自动机只需要两步：

1. 建立 trie 结构：将所有的模式串构成一棵 trie；

2. kmp 的思想：对 trie 的所有节点构造失配指针。

3.2. 概念

1. 字典树（trie）

   OI Wiki。字面意思，就是字典构成的树。有点要注意，trie 上每个节点都表示某个模式串的前缀，我们称其为状态。每个节点都表示一个状态，每条边都是状态的转移。

2. 失配指针（fail）

   AC 自动机通过一个 fail 指针进行多模式串的匹配。一个状态 $u$ 的 fail 指针指向 $v$，表示状态 $v$ 是 $u$ 的最长后缀（即在若干模式串的前缀中匹配当前状态的最长后缀）。

   失配指针和 kmp 的 next 数组虽然定义不同，但它们的功能类似，都是用来处理失配时的移动。

3.3. 流程（更具体地还是看 OI Wiki 吧，有图好懂得多）

1. 建立 trie 树；

2. 用 bfs 构建 fail 指针和自动机；

3. 匹配。

3.4. 例题

P3121 [USACO15FEB]Censoring G

题意：

有 $n$ 个模式串和 $1$ 个文本串，删除文本串中出现过的所有模式串。

思路：

想想只有一串的时候我们怎么做：kmp $+$ 栈。而现在有了多个模式串，那么我们可以想到用 AC 自动机来匹配，同时删除操作用栈来进行：记两个栈，一个用来记录 AC 自动机扫到哪里了，另一个用来记录合法的位置，若出现字符串则将栈顶位置都减去串的长度，最后答案就是合法位置。

P3041 [USACO12JAN]Video Game G

题意：

有 $n$ 个模式串，要求构造一个长度为 $k$ 的文本串，使得所有模式串在文本串中出现次数最多，求最多出现次数。

思路：

首先我们显然可以想到 dp，不过时间复杂度很大，为了优化，我们构造 AC 自动机来进行字符串的匹配。我们设 $f_{u,i}$ 表示当前匹配的点是 $u$，长度为 $i$ 的最大匹配数，转移的话用父亲来更新儿子，设 $cnt_i$ 表示以 $i$ 结尾的字符串个数

$f_{t_u.vis_j,i} = \max(f_{u,i-1}+cnt_{t_u.vis_j})$

那么 $cnt_i$ 又该如何计算呢？我们会发现，$u$ 的失配指针指向 $v$，那么说明 $v$ 代表的字符串一定是 $u$ 的前缀，因此直接累加。

P5840 [COCI2015]Divljak

题意：

有 $n$ 个字符串 $S$，有个初始为空的字符串集合，然后有 $q$ 次操作，操作有两种情况：一种是往集合中加字符串；另一种是查询集合中有多少字符串包含 $S_x$。

思路：

首先根据集合建自动机显然是不行的，因为这样的话就是动态的，很难维护。因此我们将给出的字符串构造自动机，然后我们思考 fail 指针的性质：$u$ 的 fail 指针指向 $v$，说明 $v$ 是 $u$ 的后缀，也就是出现在 $u$ 代表的字符串中，因此我们建出 fail 树。

然后对于每一个新加入的字符串 $t$，对于 $t$ 在自动机上匹配的每一个点 $t_1,t_2,\ldots,t_n$，它在 fail 树上的祖宗都一定在 $t$ 中（根据上面 fail 指针的性质），因此我们考虑 dfs 序 $+$ 树状数组（单点修改、区间查询）。

不过本题很恶心的一点是它要取的是路径的并集，否则会算重。比如 a 在 aba 中就会算两次，因此我们要用到一个神奇的技巧：将要修改的点按 dfs 序排列，然后将 $i$ 和 $i+1$ 是为一组，进行 $[i,+1],[i+1,+1],[lca(i,i+1),-1]$ 的操作，这样就不会重复了。

P2444 [POI2000]病毒

题意：

给出 $n$ 个 01 串，问是否能构造出一个无限长的字符串使得其每一个子串都不是一开始给出的字符串中的一个。

思路：

我们将一开始给出的字符串建立自动机，然后插入时将会成为字符串结尾的节点标记。然后根据 fail 的性质，若 $u$ 的 fail 指针有标记，那么 $u$ 也有标记。最后直接从 $0$ 开始 dfs，因为要构造无限长的，因此判断是否能产生环即可。

3.5. 题型

做多了题目发现有些题型十分常见，因此特意总结一下。

3.5.1. AC 自动机上 dp