【总论】字符串相关

另一种阅读体验

字符串哈希

Trie 树

在计算机科学中，trie 树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。

与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。

一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

在 Trie 上，两个字符串的最长公共前缀（LCP）就是两个点的最近公共祖先（LCA）所对应的点。

有些时候，我们也可以将数字看作一个二进制数，或者输一个由 0/1 组成的定长字符串，来解决一些问题。

KMP 算法

KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

前置知识

border 指所有那些既是前缀又是后缀，但不是本身的子串。

border 的 border 仍是 border。

一个串的所有 border 互为 border。

若 Lborder 为一个串的最长 border，那么一个串的 Lborder，Lborder 的 Lborder ... 为这个串的所有 border。

所以实际上每个前缀都指向自己的 Lborder（没有则指向超级根），可以形成一个树形结构，每个点到根的路径就是所有 border。

换句话说，$S-c$ 的 Lborder 一定是 $S$ 的一个 border 增加一个字符得到的。（注意这里没有 $L$） **怎么对 S 的每个前缀求 Lborder？** 假设我们求出了 $S$ 的所有前缀的 Lborder，那么按照刚刚的性质从长到短暴力枚举 $S$ 的所有 border $T$，找到第一个使得 $T$ 后面字符是 $c$ 的即可。 方便起见，记 $S[1][r]$ 表示 $S$ 从第 $1$ 个字符到第 $r$ 个字符形成的子串。 首先 $S[1][1]$ 的 Lborder 是 $0$。 从 $i=2$ 到 $i=n$，假设已经求出了 $S[1][1],...,S[1][(i-1)]$ 的 Lborder，现在要求 $S[1][i]$ 的 Lborder，根据刚才的讨论，只要枚举 $S[1][(i-1)]$ 的 border 即可，即令 $j=Lborder[i-1]$，然后不停的令 $j=Lborder[j]$，直到 $j=0$ 或者 $S[j+1]==S[i]$ 为止。 显然 $Lborder[i]\le Lborder[i-1]+1$，而每一轮 $j$ 跳跃次数不超过 $|Lborder[i]-Lborder[i-1]|$，由于总有 $Lborder[i]\ge 0$，所以 Lborder 变小的幅度之和不会超过变大的幅度之和，而变大的幅度之和显然是 $\text{O}(n)$ 的，因此复杂度线性。 每个 border 都与一个不严格循环节一一对应。 也就是说，如果 $m$ 是长为 $n$ 的字符串 $S$ 的一个 border，那么 $m-n$ 就是 $S$ 的一个不严格循环节，反之亦然。 因此找到一个串的所有不严格循环节，只要枚举一个串的所有 border 即可。而（严格的）循环节就是那些使得 $(m-n)|n$ 的长为 $m$ 的 border。 **AC 自动机** 考虑一个 KMP 的 EX 版本。 给定一个模板串 $T$，和若干匹配串 $S_1...S_m$，对每个 $S_i$ 询问其在 $T$ 中出现几次。 $|T|\le 100000,Si$ 总长 $\le 100000

考虑把 S 放到一块建类似 nxt 一样的东西（在 AC 自动机中叫 fail 指针）。

先将 S 建 Trie，考虑在 Trie 上运行 T。

当遇到无法匹配的情况时，希望找到 T 已匹配部分的一个最长后缀，使得这个后缀也是某个 S 的前缀。

注意这里实际上和 T 无关，我们只需要对 Trie 上每个节点对应的字符串做这件事情即可。

换句话说，我们要对每个点找到其最长后缀也是某个 S 的前缀，而 S 的前缀必然对应 Trie 上一个点，或者说我们需要找到一个失配节点（fail）。

具体的找法用一个 BFS 就能实现。

除了一些特殊情况，一个点的 fail，就是其 fail 的 fail 的对应子节点（如果有的话），没有的话就继续跳 fail。

可以证明这样做的复杂度是正确的。

匹配 T 的时候，就用 T 在 S 上面跑，每次失配就沿着 fail 指针向上跳直到可以继续匹配为止。

这样复杂度显然是线性的。

注意问题

一个点对应的字符串出现的次数需要统计子树和，比如 abcd 的对应节点出现一次，那么 bcd，cd，d 都要出现一次。

直接如此实现会有常数上的劣势，一个显著的改进方法是：若该点有 c 的出边，一个点的 ch[c] 等于其对应的儿子；否则这个点的 ch[c]= 发生失配时最终转移到的点。

只需要在求 fail 的时候，对于第二种情况（假设当前是 x）ch[x][c]=ch[fail[fa[x]]][c] 即可，注意特判根节点周围的一圈点。

这样能显著优化常数，而且在做另一些问题时能简化问题。

给 n 个串然后两两询问的题有些时候的处理方法

考虑选一个适当大小的数字 s，那么一个串长度要么不超过 s，而长度超过 s 的只有不超过 \dfrac ms 个。

若询问两个长度均不超过 s 的串，那么直接 KMP 即可，复杂度 \text{O}(s)；

若询问中有至少一个串长度超过 s，假设是 A，那么用 AC 自动机预处理所有串在 A 中出现了几次，复杂度是 \text{O}(m) 的，由于这部分 A 只有不超过 \dfrac ms，所以这部分预处理复杂度 \text{O}(\dfrac{m^2}s)。

因此总复杂度 \text{O}(qs+\dfrac{m^2}s)。

取 s=\sqrt{\dfrac{m^2}q} 时有最小值 O(\dfrac m{\sqrt{q}})。

不过大多数题 m,q 同阶，所以偷懒取 s=\sqrt{m} 也行。

具体取多少还可以适当调参来加速。（因为两部分算法有常数差异）

后缀数组 SA

SA 能在 O(n\log n) 的时间内将所有后缀按照字典序排序，然后求排名相邻的两个后缀的 LCP（最长公共前缀），结果是排序后的结果。

一个简单的推论是，两个后缀的 LCP 就是后缀数组对应位次间所有相邻字符串 LCP 的最小值，这样可以 RMQ（区间最值查询）。

可以利用 SA 求一个字符串有多少本质不同的子串（即长的不一样），或者求一个字符串的第 k 小等。

这些问题本质相同：

考虑如何按从小到大的顺序得到 s 的所有子串。

由于子串就是后缀的前缀，所有我们只需要考察所有后缀的前缀即可。

从小到大考虑 SA 中的后缀，假设考虑到了第 i 个和第 i-1 小的后缀的 LCP 是 L，那么第 i 小的后缀的长小于等于 L 的前缀都是已经考虑过的，而长大于 L 的前缀都是新出现且字典序逐渐增大的子串。

那么这两个问题解决了。

第二个问题通过二分可以 O(\log n) 回答。

同理也可以求一个子串的位次，方法是先找到所在后缀，对应到 SA 上，考虑二分出一个最小的以这个子串为前缀的后缀（即两个后缀的 LCP 长度大于等于子串长度），然后求一下现在这个后缀和前一个后缀的 LCP 即可算出该子串的位次。

因此可以用 SA 实现子串和位次的转化。

同时参照上面的方法也可以求出一个子串在哪些位置出现过。

后缀树

后缀树是一种数据结构，是前缀树里的一个特殊类型，能快速解决很多关于字符串的问题。

一个 string S 的后缀树是一个边被标记为字符串的树。

因此每一个 S 的后缀都唯一对应一条从根节点到叶节点的路径，这样就形成了一个 S 的后缀的基数树。

SAM（后缀自动机）

SAM 就是将 DFA 与后缀结合，将重复的后缀压缩成只有一个，这样省下了空间。

后缀自动机厉害的地方就在于空间时间都是线性复杂度的，十分优秀。

SAM 的每个状态 st 都包含了一部分 S 的子串，记作 substrings(st)，并且对于两个不同状态 u 和 v，包含的子串 substrings(u) ∩ substrings(v) = ∅；

每个子串都恰好被一个状态包含，所以我们只要构造出来 S 对应的 SAM，再对所有状态 st 求 Σ(maxlen(st)-minlen(st)) 就是子串的数目。

SA-IS

SA−IS 排序是基于诱导排序这种思想，将问题规模缩小，解决更小的问题，快速解决原问题的算法。

Manacher 算法

Manacher 算法，又叫“马拉车”算法，可以在时间复杂度为 \text{O}(n) 的情况下求解一个字符串的最长回文子串长度的问题。

在进行 Manacher 算法时，字符串都会进行一个字符处理，比如输入的字符为 acbbcbds，用“#”字符处理之后的新字符串就是 #a#c#b#b#c#b#d#s#。

回文自动机

同其他自动机一样，回文自动机是个 DAG（有向无环图），它用相当少（\text{O}(n)）的空间复杂度存储了这个字符串所有回文串的信息。

和别的自动机不太一样，回文自动机是有两棵树的森林：其中一棵是长度为偶数的回文串集合，另一棵是长度为奇数的回文串集合，这两棵树的根节点分别表示长度为 0（空串）和 -1（无实际含义，便于运算）的回文串。

一个回文自动机包含不超过 |S| 个节点，每个节点都表示了这个字符串的一个不重复的回文子串，同时一个节点会有不超过字符集大小的边连向其他节点，以及一条 fail 边连向这个点的 fail ...

自动机中每条有向边都有一个字符类型的权值，起点的串左右分别加上这个字符得到的就是终点的串。

举个例子：设一条边权为 c 的边连接的两个点分别是 A,B，A表示回文串 aba，则B表示的回文串就是 cabac。

特别的，如果 A 是那个长度为 −1 的根，B 串就是这条边的权值。

当你插入一个字符的时候，插入的点代表的就是这个字符匹配的最长回文串，也就是说从根节点往下顺着边走，记着一个 str 一开始为空，一边走一边不停地往 str 左右两边添加新的字符，走到一个点，这个点代表的回文串就是 str。

每个点都有个 fail 边，这条边指向这个点所代表的回文串的最长回文后缀所在的那个点（最长回文后缀：串中满足回文的最长的后缀，这个串自己不算）。

如果没有，则指向 0（就是那个根节点）。

特别的，0 的 fail 节点就是那个长度为 -1 的点。