【总论】字符串相关

[**另一种阅读体验**](https://www.mina.moe/archives/15429) *** **[字符串哈希](https://www.luogu.com.cn/blog/fsx/ha-xi)** **Trie 树** 在计算机科学中，trie 树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。 与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。 一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。 一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 在 Trie 上，两个字符串的最长公共前缀（LCP）就是两个点的最近公共祖先（LCA）所对应的点。 有些时候，我们也可以将数字看作一个二进制数，或者输一个由 $0/1$ 组成的定长字符串，来解决一些问题。 **KMP 算法** KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。 **前置知识** border 指所有那些既是前缀又是后缀，但不是本身的子串。 border 的 border 仍是 border。 一个串的所有 border 互为 border。 若 Lborder 为一个串的最长 border，那么一个串的 Lborder，Lborder 的 Lborder $...$ 为这个串的所有 border。 所以实际上每个前缀都指向自己的 Lborder（没有则指向超级根），可以形成一个树形结构，每个点到根的路径就是所有 border。 $T-c$ 是 $S-c$ 的 border（$c$ 是一个字符），那么 $T$ 是 $S$ 的 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$ 的点。