【题解】P5211 [ZJOI2017] 字符串

TallBanana · 2025-11-19 16:22:30 · 题解

引入科技——最小后缀

定义

• 记 suf(S) 表示 S 的后缀集合。
• 记 minsuf(S) 表示 S 的最小后缀。
• 记 Ssuf(S) 为 \{V\in suf(S)|\exist T,VT=minsuf(ST)\}，称为 S 的潜在最小后缀。\ 即在 S 后增加一个串 T （可以为空）后，可能成为最小后缀的串的集合。

性质

• 对于任意两个 Ssuf 中的元素 U,V，$	U	<	V	\Leftrightarrow U 是 V 的前缀。 ::::info[证明] 如果 U 不是 V 的前缀，则 UT 和 VT 的大小是由 U,V 的大小关系决定的，那么只有一者可能是 \in Ssuf 的。 这里，注意 U 是 V 的后缀，所以 U 是 V$ 的 border。

• 对于任意两个 Ssuf 中的元素 U,V，|U|<|V|\Leftrightarrow 2|U|\le|V|。 ::::info[证明] 反证，假设 |U|<|V|<2|U|，由上面的定理可得 U 是 V 的 border。于是对应 |V|-|U| 长度的周期，我们把这个周期记作 T。因为 |T|\le |V| 且 |T|\le |U|/2，于是我们可以改写 U=TC,V=T^2C。
  由最小后缀，存在 R （可空）满足： ::::
• 推论：|Ssuf(S)|=O(\log|S|)。

题解

题面传送门：[ZJOI2017] 字符串

先写个分块，支持 O(\sqrt n) 区间加，O(1) 查询区间哈希值。

考虑使用线段树维护 Ssuf 集合，查询时，答案只有可能是拆出来的 O(\log n) 个节点的 Ssuf 集合的元素，共 O(\log^2 n) 个，大力比较，复杂度是 O(\log^3n)。
修改的时候，只有被修改区间包含的 O(\log n) 个节点的 Ssuf 可能改变。 合并两个儿子的信息时，设左侧的串为 L，右侧的串为 R。显然，Ssuf(LR) 是 (Ssuf(L)+R)\cup Ssuf(R) 的子集。

由倍长定理&线段树两个儿子长度差距只有最多 1 可得，Ssuf(L) 至多有 1 个元素可以保留到 Ssuf(LR) 中。考虑如何选出那个元素。
对于 U,V\in Ssuf(L)，不妨设 UR<VR：

于是我们可以一直排除 Ssuf(L) 中的元素，直到只剩下一个元素 X，设 P=XR。 我们接下来开始计算 Ssuf(LR)，初始让集合 S=Ssuf(R)，枚举其中的串 V 进行如下操作：

• 若 V 是 P 的前缀，则什么也不干。
• 若 V 不是 P 的前缀，且 V<P，抛弃 P，停止。
• 若 V 不是 P 的前缀，且 V>P，抛弃 V。

最终如果 P 未被抛弃，则把 P 加入 S。最终 Ssuf(LR)=S。（事实上，直接让 Ssuf(LR)=Ssuf(R)\cup \{P\} 复杂度也是对的，然鹅会有 2 左右的常数） 总复杂度是 O(n\log^2 n+m\log^3 n+m\sqrt n)。