字符串笔记

P12923 [POI 2021/2022 R3] 模板 2 / Szablon 2

考察 z 函数与 dsu 的结合，主要难点在于想到暴力找前缀最后匹配复杂度为调和级数，想到做法后容易证明复杂度，以及值域 \(O(n)\) 的维护集合删点加查询前驱后继可以用 dsu 优化（无法维护加点）。

比较套路的分治，但是没有想到。记得做思路转换，没事想想套路解法。

分治后可以做 Z 函数求解，总时间复杂度 \(O(qn \log n)\)。