Lyndon 分解

参考资料

Lyndon 串 是严格小于自身所有真后缀的字符串。Lyndon 分解 把一个字符串唯一地拆成若干个字典序单调不增的 Lyndon 串的拼接，用 Duval 算法 可在 $O(n)$ 内求出。它与最小表示法、最小 / 最大后缀等问题紧密相关。

对给定字符串求其 Lyndon 分解，并输出各 Lyndon 串结尾位置下标的加权和。