3396

根号分治模板题 #include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> #include <cmath> #define RED "\033[0;32;31m" #define NONE "\033 ......

设当前询问的串为 $s_i$ 记为 $t$。考虑 $r$ 右移，维护每个 $l$ 对应的 $g(l,r)$ 和 $\max_{l}\frac{g(l,r)}{r-l+1}$ 即可。 最基本的观察是：当 $r$ 右移后，考虑 $t_{1..r}$ 在 AC 自动机上匹配到的点 $p$，那么对于 $p$ ......