Lyndon 分解

Summary

Lyndon 串是严格小于自身所有真后缀的字符串。Lyndon 分解把一个字符串唯一地拆成若干个字典序单调不增的 Lyndon 串的拼接，用 Duval 算法可在线性时间内求出。这一分解与最小表示法、字符串的最小后缀与最大后缀等问题紧密相关，是处理循环同构、字典序最小旋转一类问题的基础工具。

参考资料

• Lyndon 分解 - OI Wiki

简介

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

例题

洛谷 P6114 【模板】Lyndon 分解

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