Significant Suffixes

little_pinkpig / 2024-11-13 / 原文

$\text{Significant Suffixes}$

我们定义 $\text{ssuf}(S)$ 表示 $S$ 中可能成为最小后缀的后缀，形式化定义为

记 $\text{suf}(S)$ 表示 $S$ 的所有后缀；
记 $\text{minsuf}(S)$ 表示 $S$ 的最小后缀；
定义 $\text{ssuf}(S)$ 为 $\{x|x\in \text{suf}(S),\exists T,ST\in \text{minsuf}(ST)\}$；

下面给出 $\text{ssuf}$ 的两个性质

$\mathbf{Lemma}\;1$

对于 $U,V\in \text{ssuf}(S)$ 且 $|U|<|V|$ 有 $U$ 是 $V$ 的 $\text{border}$，证明如下：

由于 $U,V$ 都是 $S$ 的后缀，所以必定存在包含关系，所以 $U$ 是 $V$ 的后缀。

如果 $U$ 不是 $V$ 的前缀，无论向串后面加怎样的 $T$，那么 $UT$ 与 $VT$ 的大小关系由 $U$ 和 $V$ 决定，所以 $U,V$ 只有一者有可能是属于 $\text{ssuf}(S)$，矛盾，所以 $U$ 是 $V$ 的前缀。

所以 $U$ 一定是 $V$ 的 $\text{border}$.

$\mathbf{Lemma}\;2$

对于 $U,V\in \text{ssuf}(S)$ 且 $|U|<|V|$ 有 $2|U|<|V|$，证明如下：

考虑反证 $|U|<|V|\le 2|U|$，由 $\text{Lemma}\;1$ 可知 $U$ 是 $V$ 的 $\text{border}$，所以有 $|V|-|U|$ 的周期 $T$，则有 $U=TC,V=TTC$.

向串后面加入任何字符串 $R$，那么若 $UR=TCR<VR=TTCR$ 则 $CR<TCR\rightarrow CR<UR$，注意到 $C$ 也是后缀，所以 $U$ 必定不可能为最小后缀，而若是 $UR>VR$ 而 $U$ 也不可能为最小后缀，矛盾，所以 $2|U|<|V|$.

根据 $\mathbf{Lemma}\;2$，有 $|\text{ssuf(S)}|=\mathcal O(\log |S|)$.

$\text{「ZJOI2017」字符串}$

考虑用线段树合并维护 $\text{ssuf}$ 的集合，合并 $|S_1|,|S_2|$ 的 $\text{ssuf}$ 时由于 $|S_2|\le |S_1|\le |S_2|+1$ 所以 $\text{ssuf}(S_1)$ 中至多有 $1$ 个属于 $\text{ssuf}(S_1S_2)$.

考虑如何选出那个元素，设 $U,V\in \text{ssuf}(S_1)$ 不妨设 $US_2<VS_2$，如果 $US_2$ 不是 $VS_2$ 的 $\text{border}$，那么 $VS_2$ 可以排除，否则 $US_2$ 可以排除，设最后留存的为 $P$，直接使 $\text{ssuf}(S_1S_2)=\text{ssuf}(S_2)\cup\{P\}$，能够保证复杂度，但是常数较大，考虑挑出 $S_2$ 中不合理的.

然后考虑 $V\in \text{ssuf}(S_2)$，那么

若 $V$ 是 $P$ 的前缀，不做任何操作；
若 $V$ 不是 $P$ 的前缀，且 $V<P$，抛弃 $P$；
若 $V$ 不是 $P$ 的前缀，且 $V>P$，抛弃 $V$；

这样可以有效减小常数。

查询时，我们将 $\mathcal{O}(\log^2n)$ 的集合全部检查一遍，检查和合并时我们需要比较两个字符串的大小，修改时由于影响到 $\mathcal{O}(\log n)$ 个线段树节点，而且被修改区间完整覆盖的 $\text{ssuf(S)}$ 不发生变化，所以总共需要 $\mathcal{O}(n\log n+m\log^2 n)$ 次比较，考虑使用数据结构维护 $\text{Hash}$ 二分实现，这样需要 $\mathcal{O}(n\log^2 n+m\log^3 n)$ 次查询和 $\mathcal O(m)$ 次修改，由于查询和修改不平衡，可以使用 $\mathcal O(sqrt(n))$ 修改和 $\mathcal O(1)$ 查询的分块维护。总复杂度为 $\mathcal O(n\log^2 n+m\log^3 n+m\sqrt n)$.