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$ 的点。
0 条评论