结论：如果 p,q 为 s 的周期，满足 \(p+q-gcd(p,q)\le |s|\)，那么 \(gcd(p,q)\) 也是 s 的周期。
证明要用到生成函数，不会。
结论：设 \(2|a|>|b|\)，a 在 b 中匹配的位置构成等差数列。
假设第一次差 x，第二次差 y，显然 y,x 都是周期。
设最小周期为 r，那么 \(r|gcd(x,y)\)，所以 \(r|x\)。
若 \(r<x\)，那么第 1 次匹配的位置 +r 就是第二次匹配，与要求矛盾。
同理可得 \(x=y=r\)
结论：串 s 所有长度大于 \(\frac{|s|}{2}\) 的 border 长度构成等差数列。
证明是类似的。
A.[CEOI 2011] Matching
这里要重新定义相等，因为是排列，不会重复，所以只需要知道前面又几个数比他小。
所以用一个树状数组查排名 \(O(n\log n)\)
可以将匹配看作一个插入的过程，如果每次都恰好插到对应位置，那么也可以视为匹配。
所以可以预处理 p 序列中每个 i 插入时的前驱后继就可以 \(O(n)\)
B.[HNOI2019] JOJO
可持久化操作显然很扯，所以考虑离线下来建操作树。
所求的这东西就是做 kmp 然后求 \(\sum nxt\) 但是难点在于串太长了，没有办法直接弄。
可以从最后开始跳，如果发现后面有一段长度大于等于 y 的 c,可以直接结束。
但是这东西时间复杂度在有回溯的情况下一定是错的。
考虑构成等差数列的最后几个 border，设公差为 d，所以它就有一个长度为 d 的周期。
所以如果一个周期不满足时，前面的一定都不会满足，所以直接跳到前面就可以了。
每次至少串长 /2，时间复杂度 \(O(n\log n)\)
C.【UER #11】企鹅游戏
本质不同的串长只有 \(\sqrt n\) 种，然后就可以哈希暴力，\(O(L\sqrt L)\)
设一个阈值 B，长度 \(\le B\) 的串不会出现超过 LB 次 \(\ge B\) 至多 \(\frac{L}{B}\) 个，且至多出现 \(\frac{L}{B}\) 次。
所以至多有 \(LB+\frac{L}{B}\le L^{\frac{4}{3}}\) 个 \(c_i\) 不为 0，然后只处理这部分就行了。
D.String Set Queries
加串肯定是假的，考虑二进制分组。
按照 \(2^k\) 分组，然后每次加串就加一组单个的，然后不断向前合并就可以了。
E.Duff is Mad
对于长度小于 \(\sqrt L\) 的东西，随便怎么处理一下就行了。
对于剩下的串，只有不超过 \(\sqrt L\) 个，所以可以每次询问把对应的地方标上就可以了。
F.Exam
不会。
G.qoj 5034
可以把 ban 掉的限制看作一些字符串，所以可以把路径建成 AC 自动机，这里要用可持久化线段树。
然后似乎可以在这东西上面跑 dij,具体的枚举当前状态在原图上的出边，需要特殊处理 ACAM 上的没有的点。
但是因为不一一对应，时间肯定接受不了。
但是可持久化线段树上的边松弛后就没用了，所以到一个点后直接 dfs 线段树，然后删掉节点。
H.Boring Problem
相当于在 ACAM 上随机游走，可以暴力高消，但是需要减少未知数的量。
ACAM本质就是两棵树叠在一起，对于节点 x，若 c 有出边且深度大于 下，那么必然是 x 的儿子，否则就是 fail 树上的边。
设一个儿子为 \(tr_{x,i}\)，如何减少变量。
I.[POI 2012] PRE-Prefixuffix
在摆，没听。
J.[NOI2023] 字符串
条件很神秘，考虑转化，可以变成 \(s[i:i+2l-1]<R(s[i:i+2l-1])\)
后面要用后缀数组维护大小关系，不会。
K.Palindrome Partition
一个贪心的划法，每次划开最小的偶回文前后缀，然后一定会形成 2-3 个偶回文串。
就是不断在 PAM 的偶回文树上跳 fail。
L.Reverses
可以交叉把 s 和 t 插在一起，所以每次翻转后相等的一定是一个偶回文串。
然后就是相当于求一个最小划分，然后就有一个 \(n^2\) 的做法。
因为回文后缀相当于 border，而根据上面的结论，长度构成等差数列，且至多 log 种。
就可以按照这个规律去跳了。
M.[NOI2015] 品酒大会
原，不写了。
N.「JZOI-1」拜神
二分答案，找 \([l,r-x+1]\) 这个区间是否存在两个 LCP 大于 x。
按 LCP 从大到小合并 \(sa_i\) 和 \(sa_{i+1}\)，用主席树记录合并到长度为 l 时每个位置在其连通块的后继位置即可。
O.[NOI2018] 你的名字
https://www.cnblogs.com/wangsiqi2010916/p/18700045