题解

$Lyndon$串： 对于字符串$x$，如果$x$的字典序严格小于x的所有后缀的字典序，我们称$x$是简单串，或者$Lyndon$串。

近似$Lyndon$串： 若$x$为$Lyndon$串，则$xxxx′$为近似$Lyndon$串，$x′$为$x$的前缀。

$Lyndon$分解： 将一个串$x$分作$x_1x_2..x_k$，每一个部分都是$Lyndon$串，且$x_i≥x_{i+1}$。

定理

  1. $Lyndon$串是循环同构中字典序最小的一个。
  2. $Lyndon$分解唯一。
  3. 两个$Lyndon$串$a,b$，若$a<b$，有$ab$为$Lyndon$串。

考虑$i$之前的位置都已经被分解为$Lyndon$串，用指针$j$指向$i$，$k$指向$i+1$。

 - 若$x[j]=x[k]$，加上$x[k]$不会影响$i$开头的串为近似$Lyndon$串。所以比较后一位，两个指针都往后移；

 - 若$x[j]<x[k]$，我们不允许$x_i<x_i+1$，所以包含这一位。这个串是一个整体，所以使$j=i$，重新开始比较（$x[i:k]$是$Lyndon$串）；

 - 若$x[j]>x[k]$，就不行了，所以当前串就结束了；但是当前串可能是近似$Lyndon$串（$Lyndon$串的长度为$k−j$），所以一节一节来就行。

如果用后缀数组实现，可以求出所有后缀的$Lyndon$分解，其中$nex_i$表示对第i个后缀进行分解，得到的下一个$Lyndon$串的第一个位置（当前$Lyndon$串的第一个位置即$i$）。