\(\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)\).