关于串串

字符串专题 ×
数据结构专题 √

感觉不是SAM/SA就是关于border的神奇理论。由于我很菜所以做了一些偏数据结垢的东西。

[P5685]快乐的 JYY

全场最简单题，建个PAM出来两边同步走就行了giao

[P4762]Virus synthesis

二操作显然与回文有关系，PAM建出来后dp，由于二操作只能构造出偶回文，奇回文只能暴力建，于是只考虑偶回文。
一个偶回文\(s\)可以由其PAM上父亲节点转移到，步数+1
也可以通过一个长度不超过$ |s| /2 $的偶回文后缀暴力加再进行二操作得到，于是通过跳fail指针找到这个后缀转移即可

[CF1073G]Yet Another LCP Problem

比较简单的题，LCP问题先考虑求个SA，将询问的后缀按照排名排个序，逐个枚举\(a_i\)，由LCP的性质，当\(a\)的排名增大时，所有排名小于\(a\)的\(b\)的贡献是单调的，很容易想到单调栈相关的东西。于是枚举\(a_i\)，当枚举到下一个时，之前加进去的\(b\)的贡献都对\(high_{a_i}\)到$ high_{a_{i+1} }\(取了个\)\min$，值域比较小而且是全局取 \(\min\) 于是可以直接上值域线段树维护，当然如果你要写个吉司机我也不拦着你。然后再把新加进来的\(b\)算一下贡献丢到树里即可。正反扫两边，注意取等问题就没了。

[CF1286E]Fedya the Potter Strikes Back

显然要烤馍片，新加字符时把不合法的border删掉，把合法border的贡献对一个值取\(\min\)。显然暴力删border的复杂度是\(n^2\)的，把一个点的颜色设为其下一个字符，于是我们要找的就是上一个版本与所有颜色不为新加字符的border，这个可以通过类似求fail的东西预处理，这样就可以\(O(1)\)找到一个要删的border，由于最多加进去\(n\)个border，均摊下来操作次数是\(O(n)\)的，由于卡了空间，维护贡献需要用Map，插入的一个数最多在暴力取\(\min\)贡献一次复杂度，所以均摊是\(O(log n)\)的

[loj6681]yww 与树上的回文串

求所有路径的问题，观察数据范围于是先套个淀粉质，对于当前分治重心，以重心为一端或者恰好被重心平分的回文路径比较平凡，哈希一下随便求就行。对于两侧不等长的，利用结论

一个回文串的所有回文前缀可以被表示为O(logn)个等差数列

维护一下等差数列，然后建AC自动机建fail树，在fail树上做，对等差数列的公差根号分治。