Loading... 本做法参考了 [5k\_sync\_closer](https://www.luogu.com.cn/user/388651) 的文章 [如何用 Lyndon 薄纱 SA](https://www.luogu.com.cn/article/2oa4ykad) 首先有使用 SA 的做法,但是基于比较的排序的复杂度下限就是 $\mathcal{O}(n\log n)$,但是 SA 无论怎么做,当字符集较大时不能做到 $\mathcal{O}(n)$,所以这个不算严格 $\mathcal{O}(n)$。 考虑使用 Lyndon 分解,设字符串分解为 $s=w_1+w_2+\cdots+w_k$。那么根据 Lyndon 串性质,选在 $w$ 中间一定不优,于是只需要考虑选在分解的开头。 然后由于 $w$ 单调不增所以可以先找到最后一个位置 $p$,使得 $\sum_{j=p}^k|w_j|\geq i$,那么 $w_p$ 的前缀就是答案,但是这时候不一定是第一个这个子串出现的位置,所以考虑向前找到第一个 $w_{p\prime}$ 使得,$w_{p\prime}$ 前缀和 $w_p$ 相等,这个时候可以使用二分加哈希解决,复杂度 $\mathcal{O}(n\log n)$。 但是实际上不需要,考虑先求出 $\text{lcp}(w_{p-1},w_p)$,实际上这是可以 $\mathcal{O}(n)$ 做到的,观察贪心求解 Lyndon 分解时,连续的一段 Lyndon 串周期(结尾可能是不完整的一个周期)中的每个分解都有一段 lcp,两段 Lyndon 串周期之间就没有 lcp 了,所以可以直接找出 lcp。 由于分解单调不增,所以每个分解起始位置的后缀同样单调不增,所以其实这就是一个 Lyndon 分解的 height 数组,同样可以从中求得两个分解之间的 lcp,也是之间的最小值。 然后就可以考虑,从 $1$ 到 $k$ 顺次考虑每个分解,用一个单调栈维护到前面位置的 lcp。然后用一个指针指向栈中的一个位置,每次需要求的 $i$ 变小,指针向栈底调整即可。若当前指针的元素被取 min 覆盖,把指针指向栈顶即可,由于每次覆盖的时候前面的元素都被删了,所以复杂度就是严格 $\mathcal{O}(n)$。 最后修改:2025 年 01 月 11 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用,请随意赞赏