题解 P6127 【【模板】Lyndon 分解】
wucstdio
2020-02-18 16:33:06
大概是我贡献的第二道模板？
## $\text{Lyndon}$ 分解详解
我们定义一个串是 $\text{Lyndon}$ 串，当且仅当这个串的最小后缀就是这个串本身。
该命题等价于这个串是它的所有循环表示中字典序最小的。
---
#### 引理 1：如果 $u$ 和 $v$ 都是 $\text{Lyndon}$ 串并且 $u<v$，则 $uv$ 也是 $\text{Lyndon}$ 串。
证明：
##### 1、若 $\operatorname{len}(u)\ge\operatorname{len}(v)$
这时，$u$ 和 $v$ 这两个串在 $\operatorname{len}(v)$ 之前就出现了不同的字符，所以有 $v>uv$，又因为 $v$ 是 $\text{Lyndon}$ 串，所以 $v$ 的所有后缀都大于 $v$，所以 $uv$ 的所有后缀都大于 $uv$，故 $uv$ 是 $\text{Lyndon}$ 串。
##### 2、若 $\operatorname{len}(u)<\operatorname{len}(v)$
若 $u$ 不是 $v$ 的前缀，那么有 $v>uv$，得证。
若 $u$ 是 $v$ 的前缀，那么如果 $v<uv$，则必有 $v[\operatorname{len}(u)+1:]<v$（也就是各自去掉了前 $|u|$ 个字符），矛盾。
---
我们定义一个串 $S$ 的 $\text{Lyndon}$ 分解为一个字符串序列 $A_1,A_2,\dots,A_m$，满足：
- $\forall i \in [1,m]$，满足 $A_i$ 是 $\text{Lyndon}$ 串。
- $\forall i \in [1,m-1]$，满足 $A_i\ge A_{i+1}$。
可以证明这种划分存在且唯一。
### 存在性证明
初始令 $m=|S|$ 并且 $A_i=S[i]$，然后每次不断找到 $A_i<A_{i+1}$ 并且合并为一个串。最后一定能使得所有的 $A_i\ge A_{i+1}$。
### 唯一性证明
假设对于字符串 $S$ 存在两个 $\text{Lyndon}$ 分解：
$$S=A_1A_2\cdots A_iA_{i+1}A_{i+2}\cdots A_{m_1}$$
$$S=A_1A_2\cdots A_iA^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{m_1}$$
不妨设 $\operatorname{len}(A_{i+1})>\operatorname{len}(A^\prime_{i+1})$。
观察 $A_{i+1}$ 在第二种分解中的对应情况。假设 $A_{i+1}=A^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{k}A^\prime_{k+1}[:l]$。
那么由 $\text{Lyndon}$ 串的性质可知：
$$A_{i+1}<A^\prime_{k+1}[:l]\le A^\prime_{k+1}\le A^\prime_{i+1}<A_{i+1}$$
矛盾。
---
#### 引理2：若字符串 $v$ 和字符 $c$ 满足 $vc$ 是某个 $\text{Lyndon}$ 串的前缀，则对于字符 $d>c$ 有 $vd$ 是 $\text{Lyndon}$ 串。
证明：
设该 $\text{Lyndon}$ 串为 $v+c+t$。
则 $\forall i \in [2,|v|],v[i:]+c+t>v+c+t$，也就是说 $v[i:]+c\ge v$。
所以 $v[i:]+d>v[i:]+c\ge v$。
同时因为 $c>v[1]$，我们有 $d>c>v[1]$。
故 $v+d$ 是一个 $\text{Lyndon}$ 串。
---
### $\text{Duval}$ 算法
这个算法可以在 $O(n)$ 时间复杂度，$O(1)$ 空间复杂度内求出一个串的 $\text{Lyndon}$ 分解。
该算法中我们仅需维护三个变量 $i,j,k$。
维持一个循环不变式：
- $s[:i-1]=s_1s_2\cdots s_g$ 是固定下来的分解，也就是 $\forall l\in[1,g],s_l$ 是 $\text{Lyndon}$ 串且 $s_l>s_{l+1}$。
- $s[i,k-1]=t^h+v(h>1)$ 是没有固定的分解，满足 $t$ 是 $\text{Lyndon}$ 串，且 $v$ 是 $t$ 的可为空的不等于 $t$ 的前缀，且有 $s_g>s[i,k-1]$
如下图：
当前读入的字符是 $s[k]$，令 $j=k-|t|$。
分三种情况讨论：
- 当 $s[k]=s[j]$ 时，直接 $k\leftarrow k+1,j\leftarrow j+1$，周期 $k-j$ 继续保持
- 当 $s[k]>s[j]$ 时，由**引理 2** 可知 $v+s[k]$ 是 $\text{Lyndon}$ 串，由于 $\text{Lyndon}$ 分解需要满足 $s_i\ge s_{i+1}$，所以不断向前合并，最终整个 $t^h+v+s[k]$ 形成了一个新的 $\text{Lyndon}$ 串。
- 当 $s[k]<s[j]$ 时，$t^h$ 的分解被固定下来，算法从 $v$ 的开头处重新开始。
复杂度分析：$i$ 只会单调往右移动，同时 $k$ 每次移动的距离不会超过 $i$ 移动的距离，所以时间复杂度是 $O(n)$ 的。
代码如下：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[5000005];
int n,ans;
int main()
{
scanf("%s",s+1);
n=(int)strlen(s+1);
for(int i=1;i<=n;)
{
int j=i,k=i+1;//初始化
while(k<=n&&s[j]<=s[k])
{
if(s[j]<s[k])j=i;//合并为一整个
else j++;//保持循环不变式
k++;
}
while(i<=j)//从v的开头重新开始
{
ans^=i+k-j-1;
i+=k-j;
}
}
printf("%d\n",ans);
return 0;
}
```