Lyndon 串
介绍
Lyndon 串是满足本身为所有循环移位中字典序严格最小的串。
性质：$u<v$ 均为 Lyndon 串，则 $uv$ 也为 Lyndon 串。
又由于单个字符是一个 Lyndon 串，可依靠这种思想进行合并。
Lyndon 分解：将字符串 $s$ 分成 $s=s_1s_2s_3\ldots s_m$，使得每个 $s_i$ 都是 Lyndon 串，且 $\forall 1\le i<n:s_i\ge s_{i+1}$。
算法
求 Lyndon 分解有常见的两种做法：
Duval 算法
Duval 算法过程：
维护三个变量 $i,j,k$ ， $[0\ldots i-1]$ 为一些已经确定的 Lyndon 串， $[i\ldots k-1]$ 为 Lyndon 串 $t$ 进行多次重复后加一个 $t$ 的真前缀 $v$。当前处理的字符位置为 $k$ ， $j=k-len(t)$。分类讨论：
- $s[k]=s[j]$ 。直接 $k=k+1,j=j+1$。
- $s[k] > s[j]$。此时 $s[i\ldots k]$ 为 Lyndon 串，合并一下， $k=k+1,j=i$ 。
- $s[k]<s[j]$ 。此时每一个 $t$ 都为 Lyndon 串，将 $i$ 前移到 $v$ 的开头。
后缀数组+单调栈
Duval 算法虽然简便易写，但无法快速求出一个字符串中以每个字符开始的 Lyndon 分解。
利用 Lyndon 串的性质（本身为最小的后缀），构建后缀数组，沿字符串从后往前枚举，构建一个单调增的单调栈即可维护表示以 $i$ 开始、最长 Lyndon 串的右端点位置 $nxt[i]$ 数组。
例题
练习题：2020 CCPC-Wannafly Winter Camp Day3 J 简单字符串
- 题意：见链接
- 题解：对于每次询问 $(l,k)$ ，首先算出 $r=nxt[l]$ ，进行分类讨论：
- $lcp(suf(l),suf(r))=0$ ：答案必为 $[l,r-1]$ 。
- $lcp(suf(l),suf(r))>0$ ，设 $len = r-l,tot=len\cdot\left\lfloor\dfrac{lcp+len}{len}\right\rfloor$ ，即 $s[l\cdots r-1]$ 重复出现的长度。
- $tot\bmod k=0$ ：设 $remain=n-(l+tot\cdot len)$ - $remain=0$ ：此时可均分，答案为 $[l,l+\left\lfloor\dfrac {tot}{k}\right\rfloor-1]$ - $remain \ne0$ ：此时将最后一段连接到结尾，答案为 $[l+tot-\left\lfloor\dfrac{tot}{k}\right\rfloor,n]$
- $tot\bmod k\ne 0$ ：此时 $remain$ 段比循环段小，故答案为从 $l$ 开始的一段 $[l,l+len\cdot\left\lfloor\dfrac{tot/len}{k}\right\rfloor-1]$
