无限循环串的线性排序

· · 算法·理论

对串 A 定义 A^{\infty} 表示其无限重复下去得到的串。

给定 s_{1\dots n}，按 s_i^{\infty} 字典序对其排序。

题来自 山田リョウ，令 m=\sum_i|s_i|，尝试做到 \mathcal O(m)。

不妨引入 \mathcal O(n) 的 SA 和 \mathcal O(n)-\mathcal O(1) 的 RMQ。

首先 A^{\infty}<B^{\infty} 等价于 A+B<B+A，使用 SA 和 RMQ 可以 \mathcal O(1) 比较。

考虑建出 s_{1\dots n} 的 Trie 关于结束节点的虚树，需要在祖先后代间比较。

定义如下过程为 s_i 的展开: 从 s_i 结束节点往下继续走若干 s_i，直至不能匹配处加入一个叶子。

单次复杂度即 虚树上所经点数，若能按长度升序依次对所有串展开，顺序确定。

考虑优化，对原树上的点，其被经过次数和为 \mathcal O(m)，对新点考虑延后处理。

即将所有展开的串先挂在原树某个节点上，对挂在同个节点上的串按之后首个字符区分不同叶子。

此时可能出现多个串在同一节点的情况，对这些串利用性质单独排序。

设当前节点为 u，S 为 u 到根链所对应的串，t_{1\dots k} 为挂在 u 上的 s_* 原串。

则 t_{1\dots k} 均为 S 的周期，由弱周期引理若 |t_i|+|t_j|\ge |S| 可以导出 t_i^{\infty}=t_j^{\infty}。

除去这种情况，余下 t'_{1\dots k'} 中至多一个长度 <\frac{|S|}{2}，做 \mathcal O(k'\log k') 排序即可。

原因是 |S|\cdot k' 和 \sum_{i=1}^{k'}|t'_i| 同阶且 k\le |S|，故排序复杂度之和 \mathcal O(m)，总复杂度 \mathcal O(m)。

似乎有更简单做法，如有更好做法或错误之处请指出！