Lyndon 分解 学习笔记
dyc2022
·
·
题解
更好的阅读体验
Lyndon Word 与 Lyndon 分解
$\text{Lyndon}$ 分解：将一个字符串 $s$ 分解为若干个 $\text{Lyndon}$ 串 $s = w_1 w_2 \cdots w_k$，且满足 $w_1 \sim w_k$ 在字典序上单调不增。
可以证明，一个字符串的 $\text{Lyndon}$ 分解存在且唯一。
> 首先，将一个字符串分解为若干个 $\text{Lyndon}$ 串（不考虑字典序不增）的方案显然存在，此时直接令每个字符均为一个 $\text{Lyndon}$ 串即可。
>
> 接下来考虑证明，若 $u, v$ 是 $\text{Lyndon}$ 串且满足字典序 $u < v$，则 $uv$ 也是 $\text{Lyndon}$ 串。则等价于证明 $uv$ 是 $uv$ 的非平凡循环同构字符串中，字典序的严格最小者。
>
> 若一个循环同构串的开头位于 $uv$ 中 $u$ 的部分，则该循环同构串存在一个前缀为 $u$ 的后缀。由于 $u$ 的字典序 $< u$ 的任一后缀，因此 $uv$ 的字典序严格小于该循环同构串。
>
> 否则若循环同构穿的开头位于 $v$ 的部分，由于 $v$ 的任一后缀字典序 $> v$ 的字典序，因此只需要考虑循环同构串形如 $vu$ 的情况。
>
> 当 $u$ 不是 $v$ 的前缀，则 $v$ 和 $u$ 在前 $\min\{|u|, |v|\}$ 个字符内已有不同字符，因此此时一定满足 $uv < vu$。否则若 $u$ 是 $v$ 的前缀，假设 $v < uv$，则 $v[|u|+1: |v|] < v$，与 $v$ 任一后缀字典序均 $> v$ 矛盾。
>
> 因此可以每次合并两个相邻的字典序递增的 $\text{Lyndon}$ 串直到不能操作，即可得到一组 $\text{Lyndon}$ 分解。
## Duval 算法
近似 $\text{Lyndon}$ 串：称一个字符串 $s$ 是近似 $\text{Lyndon}$ 串，当且仅当可以将 $s$ 写成 $s = www\cdots w\overline{w}$，其中 $w$ 是一个 $\text{Lyndon}$ 串，$\overline{w}$ 是 $w$ 的一个前缀。
$\text{Duval}$ 算法的过程是：将我们需要求解 $\text{Lyndon}$ 的字符串 $s$ 分为三个部分 $s = s_1 s_2 s_3$，其中 $s_1$ 的 $\text{Lyndon}$ 已经求得，$s_2$ 是一个近似 $\text{Lyndon}$ 串，$s_3$ 是我们未处理的部分，通过不断扩展 $s_1$ 直到整个字符串的 $\text{Lyndon}$ 分解被求得。
我们可以在算法的过程中动态维护 $s_2$ 在 $s$ 中的位置。我们维护指针 $i$ 表示 $s_2$ 首字符的位置，$j$ 表示 $s_3$ 首字符的位置，$k$ 表示**若**将 $j$ 收入 $s_2$ 中，它在 $s_2$ 中上一个循环节的对应位置。接下来考虑处理字符 $s[j]$。
- 若 $s[j] = s[k]$，则直接将 $j$ 收入 $s_2$，令 $j \leftarrow j+1, k \leftarrow k+1$ 即可。
- 若 $s[j] > s[k]$，则 $s_2 s[k]$ 成为了一个 $\text{Lyndon}$ 串。**注意由于此时并不知道会不会有其他字典序更大的 $\text{Lyndon}$ 串并入，因此无法直接将此时的 $\boldsymbol {s_2}$ 作为 $\text{Lyndon}$ 分解的一部分加入 $\boldsymbol{s_1}$，而是只能将其作为近似 $\text{Lyndon}$ 串的一个循环节。** 此时 $j \leftarrow j+1, k \leftarrow i$，表示加入 $s[j]$ 后 $s_2$ 变成了一个仅循环一次的近似 $\text{Lyndon}$ 串。
- 若 $s[j] < s[k]$，则若加入 $s[k]$ 则 $s_2$ 不再满足近似 $\text{Lyndon}$ 的性质。此时应该将 $s_2$ 中的 $\text{Lyndon}$ 串循环节逐个加入 $s_1$，因为此时后面不可能有字典序更大的 $\text{Lyndon}$ 串拼接。那么由于一个循环节的长度为 $j - k$，因此我们每次将 $s[i: i + j - k - 1]$ 加入 $\text{Lyndon}$ 分解中，并令 $i \leftarrow i+j-k$ 即可。
注意到一个字符最多进行 $3$ 次指针移动的操作，因此时间复杂度为 $O(n)$。
## 实现
```cpp
#include<bits/stdc++.h>
#define endl '\n'
#define N 5000006
using namespace std;
int n,ans;
char s[N];
main()
{
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<=n;)
{
int j=i+1,k=i;
for(;j<=n&&s[k]<=s[j];j++)k=(s[k]<s[j]?i:k+1);
while(i<=k)ans^=i+j-k-1,i+=j-k;
}
printf("%d\n",ans);
return 0;
}
```
## Reference
- [题解 P6127 【【模板】Lyndon 分解】- 洛谷专栏](/article/lt2rnl6d) by @[wucstdio](/user/54214)。
- [Lyndon 分解 - OI Wiki](https://oi-wiki.org/string/lyndon/)。