有点 border 理论，后面忘了。
【模板】失配树
考虑现在的两个点是 \(x,y\)。如果 \(x-nxt_x=y-nxt_y\)，那么两个点可能在一条链上，先特判掉。
否则选取靠后的一个操作。考虑其周期 \(d=x-nxt_x\)。
若 \(2d>x\)，直接跳。
否则，周期可以直接跳完，\(x=x\bmod d+d\)。
那么这样跳就是 \(O(\log n)\)。
[WC2016] 论战捆竹竿
首先我们跑出这个字符串的所有 border，对于一个 border \(x\)，能加入的值就是 \(n-x\)。
根据 border 定理，一个字符串的所有 border 可以划分成 \(O(\log n)\) 个等差数列，我们考虑一个一个等差数列做。
记一个等差数列是 \(x,x+d,\dots,x+kd\)。如果当前的剩余系是 \(\bmod x\) 的，那么就可以用单调队列优化转两圈的转移。
这样我们只需要支持两个同余系互相转化，这个也是简单的，将某一个看成一个新的物品放到新的同余系中转移一次即可。
这样子的复杂度就是 \(O(n\log n)\) 的，或许可以利用所有 border 等差数列首项之和是 \(O(n)\) 的性质做到更优的复杂度，但是已经足够了。
另外我也不知道为啥这个题 uoj 和我本地跑出了 1:10 的交换比。
HDU3791 Tokitsukaze, CSL and Palindrome Game
首先有歌唱王国的结论，然后就变成比较 border 集合的字典序，
建回文自动机，然后像 SA 一样比一比字典序就好了。复杂度 \(O(n\log n)\)。
CF1483F Exam
首先我们枚举大的那个串，枚举小的那个串在大的那个串里面匹配在 \(i\)，则只有 \(i\) 往前匹配最长的串可能成为小的串，因此答案是 \(O(\sum|s_i|)\) 级别的。
对于当前串，我们将所有可能成为答案的串拎出来。如果某一个可能成为答案的串在大串上的区间被另一个区间包含，则小的区间是没戏的，因此我们先排除掉这些不能成为答案的。
然后再有不能成为答案的，那么小的串就是要是大的串的后缀了，这样就可以在 ACAM 上用 dfs 序+排序解决。时间复杂度 \(O(n\log n)\)。
ICPC Shenyang Regional M. String Problem
听说有一车做法。
首先我们发现显然对于每个前缀，最大子串的右端点都是到 \(i\) 的，所以我们只需要计算左端点。
考虑在上一次的基础上扩展出当前的答案。手玩一下可以发现，是在上一次的基础上保留一个 border，然后加上当前的字符。保留的 border 是最前面的替换之后更优的位置。
找到这个位置可以考虑在每个位置记一个 \(trs_{i,j}\) 表示跳 border 最前面的后一个为 \(j\) 的是那个，也可以利用只有 \(\log\) 个等差数列直接往前跳。
复杂度 \(O(n\log n)\) 或者 \(O(n|\sum|)\)。
跑不过 Lyndon 跑不过 Lyndon 跑不过 Lyndon。
CF1276F Asterisk Substrings
将所有本质不同子串分成带 * 的和不带 * 的。如果不带，那么 SAM 可以简单计算出有几个本质不同子串。
如果是带 * 的，那么建立正反两个 SAM，然后考虑正串 SAM 上的每个节点，对应一个 endpos 集合。则这个集合内的左区间是相同的连续一段，右区间可以表示为这些 endpos 集合对应的在反串上的链和，这个可以按照 dfs 序排序以后用线段树合并维护，做到 \(O(n\log n)\)。如果是用启发式合并 set 可以做到 \(O(n\log ^2n)\)，并且跑得可能比线段树合并快。
[CTSC2016] 香山的树
按照正常的数位 DP，变成 \(O(n|\sum|)\) 次查询固定前缀，后面任选的好串个数。
首先我们考虑如果不固定前缀，查询长度为 \(n\) 的个数怎么求。如果不考虑有整周期的情况，也就是说所有串的最小值出现位置只有 \(1\) 次。那么好的串的数量就是 \(\frac{|\sum|^n}{n}\) 。
然后考虑有循环串的情况，这个可以用莫反解决，大概就是和 \(\mu\) 作狄利克雷卷积得到的结果。
固定前缀会有更多的限制。首先就是和这个前缀匹配的时候不能小于这个前缀，这个可以对这段前缀预处理 KMP 自动机处理掉。然后我们设 \(dp_{i,j,k}\) 表示整个字符串的第 \(i\) 个位置匹配到第 \(j\) 个位置，这段前缀出现了 \(k\) 次的方案数。最后如果没有有整周期的串的话，那么方案数就是 \(\frac{1}{k}\)，有整周期的仍然可以用莫反解决。
这样直接暴力 DP 复杂度是 \(O(n^3|\sum|)\) 的，全部复杂度是 \(O(n^4|\sum|^2)\) 的，已经可以通过。不过注意到因为要求任意一个字符串不能严格小于这段前缀，所以 KMP 自动机上只有两种转移，所以可以做到 \(O(n^4|\sum|)\)，不过我没写（