浅谈 \text{Lyndon Word}
前置知识，约定与定义
一个字符可以看成一个长度为 $1$ 的字符串。
字符和字符串没有特别区分，注意区别。
对于一个字符串 $s$，记其长度为 $|s|$。对于两个字符串 $u,v$，记 $uv$ 为两个字符串按顺序拼接成为的新字符串，对于 $n$ 个字符串 $s_1,s_2,\dots,s_n$，同理记 $s_1s_2\dots s_n$ 为 $n$ 个字符串拼接形成的新字符串。请注意，$s_is_{i+1} \dots s_j$ 有特别区分 $s[i\dots j]$ 这一部分。如果单取一个字符串 $s$ 中的第 $x$ 个字符，则直接写为 $s[x]$。
定义 $\operatorname{pre}(s,x)$ 为 $s$ 的前缀，长度为 $x$；$\operatorname{suf}(s,x)$ 为 $s$ 的后缀，长度为 $x$。真前缀定义为对于字符串 $s$，使得$v=\operatorname{pre}(s,x)$ 且 $x \neq |s|$，$v$ 即是 $s$ 的真前缀，真后缀同理。
若 $0 \leq r < |s|$，满足 $\operatorname{pre}(s,r)=\operatorname{suf}(s,r)$，即称 $\operatorname{pre}(s,r)$ 为 $s$ 的 $\operatorname{border}$。长度为 $k$ 的 $\operatorname{border}$ 即 $\operatorname{pre}(s,k)=\operatorname{suf}(s,k)$。
$s \gg t$ 表示 $s>t$ 且 $t$ 不是 $s$ 的前缀。
对于一个字符串 $s$，$s^r$ 为它的反串。
对于一个字符串 $s$，$s^a$（$a$ 为一个具体数值）表示 $a$ 个 $s$ 相拼接。
## 定义
### $\text{Lyndon Word}$ 定义
定义一个字符串 $s$ 为 $\text{Lyndon Word}$，当且仅当 $s$ 是所有后缀中最小的。
简单来说，如果 $s$ 满足其最小后缀为 $s$ 本身的串，即为 $\text{Lyndon Word}$。也就是 $\forall i \in [1,|s|),s<\operatorname{suf}(s,i)$。
在 Wiki 上还有另外一个等价的定义：$s$ 是其所有循坏位移中最小的一个。相对来说上面那个会好理解一些。
### $\text{Lyndon}$ 分解定义
$\text{Lyndon}$ 分解即是将字符串 $s$ 分解成 $s_1,s_2,\dots ,s_n$，使得 $\forall i \in [1,n],s_i$ 为 $\text{Lyndon Word}$，并且 $\forall 1 \leq i < n:s_i \geq s_{i+1}$。
## 性质
#### 引理 1
若两个字符串 $u,v$ 为 $\text{Lyndon Word}$ 并且 $u<v$，则 $uv$ 同为 $\text{Lyndon Word}$。
证明：
考虑分类讨论长度大小关系：
1，若 $|u|>|v|$：
因为 $v$ 是一个 $\text{Lyndon Word}$，所以 $v$ 的所有后缀大于 $v$；考虑证明 $v>uv$，因为 $v>u$，显然；
2，若 $|u| \leq |v|$：
- 如果 $u$ 不是 $v$ 的前缀，显然 $v>uv$；
- 如果 $u$ 是 $v$ 的前缀，若 $uv$ 不为 $\text{Lyndon Word}$，也就是 $v<uv$，则有 $\operatorname{suf}(v,|v|-|u|)<v$，而这和 $v$ 是 $\text{Lyndon Word}$ 矛盾，故得证。
#### 引理 2
$\text{Lyndon}$ 分解唯一。（唯一性）
证明：
假设有两种 $\text{Lyndon}$ 分解使得分解不唯一，则：
$$s=s_1s_2 \dots s_is_{i+1} \dots s_n$$
同时有：
$$s=s_1s_2 \dots s_i's_{i+1}' \dots s_m'$$
假设 $|s_i| > |s_i'|$，且令 $s_i=s_i's_{i+1}'\dots s_k' \operatorname{pre}(s_{k+1}',l)$，所以有 $s_i < \operatorname{pre}(s_{k+1}',l) \leq s_{k+1}' \leq s_i' <s_i$，推出矛盾，故分解唯一。
#### 引理 3
对于每一个字符串，都有其 $\text{Lyndon}$ 分解。（存在性）
证明：
假设在开始的时候有 $n$ 个长度为 $1$ 的字符串 $s_1,s_2,\dots ,s_n$，我们对于每一次合并，只需要将相邻的两段 $s_i < s_{i+1}$ 进行合并就行了。
#### 引理 4
如果字符串 $v$（$|v|=r-1$） 与某个字符串 $c$（$|c|=1$），满足 $vc=\operatorname{pre}(s,r)$（满足 $s$ 是一个 $\text{Lyndon Word}$），则对于一个字符串 $d$（$d>c$ 并且 $|d|=1$），使得 $vd$ 是一个 $\text{Lyndon Word}$。
证明：
设 $s=vct$，则 $\forall i \in[2,|v|],\operatorname{suf}(v,|v|-i+1)ct>vct$，因而 $\operatorname{suf}(v,|v|-i+1)c\geq v$。且 $d>c$，所以 $\operatorname{suf}(v,|v|-i+1)d>\operatorname{suf}(v,|v|-i+1)c\geq v$。
因为 $\forall i \in [1,|v|]:c>v[i]$，所以有 $d>c>v[1]$，得证。
#### 引理 5
设有三个字符串 $s_1,s_2,s_3$，其中 $s_1$ 是一个 $\text{Lyndon Word}$ 并且 $s_1>s_2\geq s_3$。那么 $s_1>{s_2}^2\geq s_2+s_3$。
证明：
- 如果 $s_2$ 为 $s_1$ 的后缀，根据定义有 $s_1>\operatorname{pre}(s_1,|s_2|)>s_2 \geq s_3$，成立；
- 如果 $s_2$ 不为 $s_1$ 的后缀，显然成立。
#### 性质 1
如果 $s$ 为 $\text{Lyndon Word}$，则 $s$ 不存在 $\operatorname{border}$。
证明：
如果 $s$ 存在 $\operatorname{border}$，则根据 $\operatorname{border}$ 的定义，存在某个前缀等于后缀，因此这个后缀小于整个串，得证。
#### 性质 2
如果 $s$ 是 $\text{Lyndon Word}$，$s=uv$ 且 $|u|>0,|v|>0$，满足 $u<v$。
$u<uv$ 而 $uv<v$，所以 $u<v$。
#### 性质 3
如果 $|s|>2$，$s$ 是一个 $\text{Lyndon Word}$ 充要条件是满足 $s=uv$，且 $|u|>0,|v|>0,u<v$ 并且 $u,v$ 都是 $\text{Lyndon Word}$。
证明：
- 充分性：查引理 1；
- 必要性：
假设有字符串 $s$ 有后缀 $\operatorname{suf}(s,|s|-i+1)$，满足其是 $s$ 的次小后缀。
又假设 $\operatorname{pre}(s,i-1)$ 有长度为 $k$ 的 $\operatorname{border}$，而 $k<i-1$，所以 $k+1 \neq i$。
因为 $s$ 是 $\text{Lyndon Word}$，而 $\operatorname{suf}(s,|s|-i+1)$ 是其次小后缀，所以 $\operatorname{suf}(s,|s|-i+1)<\operatorname{suf}(s,|s|-k)$，所以 $\operatorname{suf}(s,|s|-i+k+1)<s$，与假设 $s$ 是一个 $\text{Lyndon Word}$ 矛盾，所以假设不成立，$\operatorname{pre}(s,i-1)$ 没有 $\operatorname{border}$。
根据 $s$ 是一个 $\text{Lyndon Word}$ 和 $\operatorname{pre}(s,i-1)$ 没有 $\operatorname{border}$ 可以推出：$\forall 1<j \leq i-1$，$\exists j \leq k \leq i-1$，满足 $s[k]>s[k-j+1]$，也就是 $s[j\dots i-1]>\operatorname{pre}(s,i-1)$，所以 $\operatorname{pre}(s,i-1)$ 是一个 $\text{Lyndon Word}$。
而 $\operatorname{suf}(s,|s|-i+1)$ 是 $s$ 的次小后缀，不存在 $j>i$，使得 $\operatorname{suf}(s,|s|-j+1)<\operatorname{suf}(s,|s|-i+1)$，所以 $\operatorname{suf}(s,|s|-i+1)$ 是一个 $\text{Lyndon Word}$。
综上，因为 $s=\operatorname{pre}(s,i-1)\operatorname{suf}(s,|s|-i+1)$，而 $\operatorname{pre}(s,i-1)$ 和 $\operatorname{suf}(s,|s|-i+1)$ 均为 $\text{Lyndon Word}$，得证。
证明了这些性质，主要是用于介绍下面的算法及题目。
## 算法
不难想到 二分+Hash 和 后缀数组 的做法，下面只介绍专用的算法。
### $\text{Duval}$ 算法
$\text{Duval}$ 算法可以在 $O(n)$ 的时间复杂度和 $O(1)$ 的**额外**空间复杂度求出一个串的 $\text{Lyndon}$ 分解。
在整个算法流程中维护三个变量 $i,j,k$。$i$ 的意思是接下来开始划分的位置，意为 $[1,i-1]$ 区间内的字符都已经划分成功。
类似于维护一个循环不变式：
- $\operatorname{pre}(s,i-1)=s_1s_2\cdots s_g$ 已经固定，并且对于任意 $l$ 满足 $s_l$ 为 $\text{Lyndon Word}$，$s_l \geq s_{l+1}$；
- $s[i \dots k-1]=t_1t_2\cdots t_hv(h\geq 1)={t_1}^hv$ 还没有固定，满足 $t_1$ 是 $\text{Lyndon Word}$，$t_1=t_2=\dots=t_h$，$v$ 是 $t_h$ 的真前缀（在这里空串是允许的），且有 $s_g \gg s[i\dots k-1]$。
这里就直接截 pdf 里面的图了。（其实是懒）
由图可见，$[1,i-1]=s_1s_2\dots s_g$ 已经分解完毕，$[i\dots k-1]=t^hv$，我们正准备加入 $k$。
流程可以表示成维护指针 $j \gets i,k \gets i+1$，循环分类判断：
- 若 $s[k]>s[j]$，由引理 4 得到 $v+s[k]$ 为一个 $\text{Lyndon Word}$。根据 $\text{Lyndon}$ 分解的要求，必须 $s[i] \geq s[i+1]$，则往前合并，所以 $j \gets i,k \gets k+1$；
- 若 $s[k]=s[j]$，有一定可能比原来的小，$j \gets j+1,k \gets k+1$，继续查找，周期保持；
- 否则这里一定要进行划分，$t_h$ 固定，退出循环，重新开始。
可以证明一个字符最多经过 $3$ 次，因此时间复杂度为 $O(n)$。
[【模板】$\text{Lyndon}$ 分解](https://www.luogu.com.cn/problem/P6114)
真·板子题。
```cpp
#include<cstdio>
#include<cstring>
char s[5000005];
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
int i,j,k,ans=0;
i=1;
while(i<=len)
{
for(j=i,k=i+1;k<=len && s[k]>=s[j];++k)
if(s[k]>s[j]) j=i;
else ++j;
while(i<=j) ans^=(i+k-j-1),i+=k-j;
}
printf("%d",ans);
return 0;
}
```
另外，这个算法可以用同样的思路求出所有 $s$ 前缀字符串的最大/小的后缀与 $s$ 的最小表示。可以自己思考上手实验。
## 从入门到进阶
[CF564E Cutting the Line](https://www.luogu.com.cn/problem/CF594E)
因为这道题实在是钛毒瘤啦，于是借鉴了一下 [wcstdio](https://www.luogu.com.cn/user/54214) 与 [xht37](https://www.luogu.com.cn/user/100544) 的题解。
分类讨论。下文中的 $n=|s|$。
### $k=1
输出 s 与 s^r 两个间小的一个。
k=n
相当于每一个字符都有反转的机会。现在要求的问题是给定 s^r，每次截取一个后缀，拼接于当前字符串之后。显然可以使用 \text{Lyndon} 对 s^r 进行分解。
k<n
相比 k=n 的情况，我们的操作没有那么随心所欲了。分析发现有两种情况可以合并：
- 若截取的字符串相同，两次操作合并为一次；
- 若截取的字符串都是回文串，两次操作合并为一次并进行反转。
k>2
有了上面发现的情况，我们考虑指定一个策略进行执行：
设 s^r 的 \text{Lyndon} 分解为 s_1,s_2,\dots,s_p,t_1,t_2,\dots ,t_q，满足 s_p \not = t_1 = t_2 = \cdots = t_q（多次加入相同字符串）或者 |s_p|>|t_1|=|t_2|=\cdots = |t_q| =1 （这个字符串长度为 1，一定满足其为回文串）。取出 t_1t_2\dots t_q，接下来继续按这个策略执行。直至 k \leq 2。同时我们可以发现，k=n 的特殊情况也是这样的。
k \leq 2
k=1
上文已经讨论。
k=2
现在我们把字符串分成两个部分。继续分情况讨论。
即 s。
即 s^r 的最小表示。
枚举字符串断开的位置。反转后缀取最优答案。直接处理是 O(n^2) 的，我们可以考虑使用拓展 \text{KMP} 算法（即 \text{Z-Algorithm}）预处理，达到 O(1)。
原问题可以转化为 (s^r[i,j-1])^r+\operatorname{pre}(i-1) 与 s^r 的字典序。这个问题可以通过两次询问解决：
两个问题都与 s^r 有关，所以说可以用拓展 \text{KMP} 算法解决这个问题。
设 s^r 的 \text{Lyndon} 分解为 a_1^{x_1}a_2^{x_2}\dots a_e^{x_e}，令 b_i=a_i^{x_i}，满足 a_1>a_2>\cdots>a_e。又令 B(i)=b_ib_{i+1} \dots b_e。
性质 1：存在整数 f \in [1,e]，使得 t_1=B(f) 并且答案最优。
这条性质等价于在 b_g,b_{g+1}(1 \leq g \leq e-1) 间进行划分能够得到最优解。
证明：
- 如果截取的位置恰巧在 a 的分割线上，那么分割线左右都是两个相等的串 a_k。这样的话这个 a 的两个端点至少有一个答案不会更差；
- 如果截取的位置不在 a 的分割线上，假设截取的位置在 a_k 中间。因为 a_k 是 \text{Lyndon Word}，所以截取的位置可以往左挪动直到 a 的分割线上更优。
性质 2：B(i)>B(i+1)。
根据引理 5 得证。
根据这个性质，我们可以得到更多的东西。观察发现，取最后一个使得 B(p) 不是 B(p-1) 的前缀的 p，因为前面已经讨论得到了 t_1=B(p) 优于前面的任何 B(i)。即若最优答案中 t_1=B(i)，满足 i \geq p。
性质 3：|B(i+1)| \leq \dfrac{|B(i)|}{2}。
（图源 wcstdio，其中的 SB_i 即 B(i)）
根据定理 3，我们能够得到一个优秀的算法——我们只需要找到最大的 $q$ 使得 $B(q)$ 比 $B(q-1)$ 优秀即可。令 $t_1=B(q)$，此时的答案最优。
于是我们考虑从 $B(m)$ 开始往前暴力比较，时间复杂度 $O(n)$。
综上，问题解决。如果有问题再评论区说说吧。思路打完一遍都不敢检查了（
代码太丑不敢放了。
## 参考文章
1. [CF564E wucstdio 题解](https://blog.csdn.net/luositing/article/details/104092435)；
2. [$\text{Lyndon Word}$ 学习笔记](https://blog.csdn.net/qq_36797743/article/details/89191890)；
3. [P6127 wucstdio 的题解](https://www.luogu.com.cn/blog/wucstdio/solution-p6127)；
4. [Wiki](https://en.wikipedia.org/wiki/Lyndon_word)；
5. [字符串算法选讲（下载链接已挂，此为预览）](https://wenku.baidu.com/view/850f93f4fbb069dc5022aaea998fcc22bcd1433e.html)。
如有不对请指出。