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 数组这样的东西，如有错误敬请指出。