题解 SP8093 【JZPGYZ - Sevenk Love Oimaster】

唐一文 · 2021-10-09 12:15:11 · 题解

根号分治。

设一个阈值 B，长度大于 B 的查询串不超过 \dfrac{\sum|q_i|}{B} 个，对这些串直接跑暴力复杂度 O(\dfrac{\sum|q_i|}{B}\sum|s_i|)。

长度不大于 B 的串预处理答案。枚举模板串中长度为 1\sim B 的所有子串，记录下它们的出现次数。可以用哈希优化，复杂度 O(B\sum|s_i|)。

总复杂度 O(\dfrac{\sum|q_i|}{B}\sum|s_i|+B\sum|s_i|)，B 取 \sqrt{\sum|q_i|} 时最优。但是我比较懒判重时直接用的 \text{set}，所以多了个 \log（。

Code