Lyndon分解 学习笔记
什么是 \(Lyndon\) 串
我们定义一个串是 \(Lyndon\) 串，当且仅当这个串的最小后缀就是这个串本身。
也就是说 \(Lyndon\) 串等价于这个串是它的所有循环表示中字典序最小的。
\(Lyndon\) 分解定义
将一个字符串 \(S\) 分解为若干个子串：\(s_1s_2s_3\dots s_m\)。对于任意 \(i\in [1,m]\)，使得 \(s_i\) 为 \(Lyndin\) 串，且 \(\forall i\in[1,m-1],s_i\ge s_{i+1}\)。
一些性质
-
若 \(u,v\) 都为 \(Lyndon\) 串，且 \(u<v\)，那么 \(uv\) 一定为 \(Lyndon\) 串。
证明：
如果想要证明 \(uv\) 是 \(Lyndon\) 串，就要证明 \(uv\) 是其最小后缀。
也就是只需要证明 \(uv<v\)，由于 \(u<v\)，那么显然成立。
-
存在性
证明：
我们可以吧所有字符单独成立一个字符串，然后根据上面那一条性质，我们可以不断找到 \(s_i<s_{i+1}\) 的，将这两个进行合并（合并之后还为 \(Lyndon\) 串），最后肯定能弄成所有 \(s_i\) 都是 \(Lyndon\) 串且 \(s_i\ge s_{i+1}\) 的。
-
唯一性
证明：
我们设有两种分解方式分别为：
\(s_1s_2s_3\dots s_{i-1}s_{i}s_{i+1}\dots s_m\)
\(s_1s_2s_3\dots s_{i-1}s_{i}'s_{i+1}'\dots s_k'\)
我们发现从第 \(i\) 个 \(Lyndon\) 串开始两种分解方式开始不一样了，我们不妨设 \(s_i=s_i's_{i+1} 's_{i+2}'\dots s_p'[:l]\)，其中 \(s_p'[:l]\) 表示第 \(p\) 个字符串的前 \(l\) 个字符组成的字符串。
我们可以因为 \(Lyndon\) 分解的定义推断出 \(s_i'\ge s_{i+1}'\ge s_{i+2}'\ge \dots\ge s_p'[:l]\)。
那么因为 \(s_i'\) 是 \(s_i\) 的前缀，那么 \(s_i'<s_i\)，所以 \(s_i>s_i'\ge s_{i+1}'\ge s_{i+2}'\ge \dots\ge s_p'[:l]\)。
然后又因为 \(s_i\) 也为 \(Lyndon\) 串（也就是说 \(s_i\) 是其所有子串中最小的），那么 \(s_i>s_i'\ge s_{i+1}'\ge s_{i+2}'\ge \dots\ge s_p'[:l] >s_i\)。
\(s_i>s_i\) 显然不成立，所以分解是唯一的。
Duval算法
考虑分为三个部分：第一部分已经分解完的，第二部分正在分解的，第三部分还没分解的。
\(Duval\) 的算法思想是保证第二部分是 \(Lyndon\) 串的情况下，然第二部分的元素越多越好。
我们维护三个变量：\(i,j,k\)。
\(S[1,i-1]=s_1s_2\dots s_q\) 表示已经固定下来的分解，其中 \(s_i>s_{i+1}\)，
\(S[i,k-1]=|t|^p+v\) 表示是还没有确定下来的分解，对于循环的 \(|t|\) 他们一定是满足 \(t_i>t_{i+1}\) 的，所以把他们分在一起。
那么我们就能设当前第二部分开头的位置为 \(i\)，要加入第二部分的指针为 \(k\)，\(j\) 为 \(|t|\) 这个循环中的，将 \(j\) 与 \(k\) 这两个位置上的字符进行比较，那么：
-
当 \(s_k=s_j\) 时，没有什么问题，直接匹配下一个字符。
-
当 $s_k>s_j $ 时，加入的字符后第二部分还是一个 \(Lyndon\) 串。
-
当 $s_k<s_j $ 时，\(t_1,t_2\dots t_h\) 的分解被固定下来，算法从 \(v\) 重新开始。
Code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch;
ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*f;
}
int main(){
int n,ans=0;
char s[5000005];
scanf("%s",s+1);
n=strlen(s+1);
int i=1;
while(i<=n){
int j=i,k=i+1;
while(k<=n&&s[j]<=s[k]){
if(s[j]==s[k]) ++j;
else j=i;
++k;
}
for(;i<=j;i+=(k-j))
ans^=(i+k-j-1);
}
printf("%d",ans);
return 0;
}