P5108 仰望半月的夜空 使用 Lyndon 分解做到严格 O(n)

本做法参考了 5k_sync_closer 的文章 如何用 Lyndon 薄纱 SA

首先有使用 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)$。

本文可能有误，毕竟似乎没人提到过 Lyndon 分解的 height 数组这样的东西，如有错误敬请指出。