T1
倒着推
T2
记每个字母上次出现位置 \(f_i\)，对应的 \(f_i\) 都相等时字符串等价，跑kmp
T3
质因数分解，前缀和维护指数，记hash
线性筛预处理每个数最小质因子，做质因数分解
T4
奇技淫巧奇思妙想
将串的权值转化为如上式子，可以发现如果两个串都在 \(A\) 集合时贡献为 \(+lcp\)，都在 \(B\) 集合时贡献为 \(-lcp\)，一个在 \(A\) 集合一个在 \(B\) 集合时没有 \(lcp\) 贡献
kmp
子串
P2375
匹配 \(next\) 时如果超过 \(\frac{n}{2}\) 就跳到当前 \(next\) 上再匹配直到小于 \(\frac{n}{2}\)
P3193
\(dp_{i,j}\) 维护扫到第 \(i\) 个字符匹配长度为 \(j\)
枚举下一个字符填什么转移方案数
由于 \(j\) 一定从 \(j-1\) 转移，可写成矩阵，用矩阵快速幂优化
manacher
