(newcommandmmathbf) (newcommandttexttt)
(text{By DaiRuiChen007})
约定：
- 对于两个字符串 (S,T)，用 (ST) 表示将 (T) 接在 (S) 后面得到的字符串（即 (S+T)）
- 对于两个字符串 (S,T)，若 (S) 的字典序严格小于 (T) 的字典序则即 (S<T)，若在满足 (S<T) 的前提下满足 (S) 不是 (T) 的前缀，我们记 (Sll T)，同理能够得到 (S>T) 和 (Sgg T) 的定义
一、Lydon Word
I. Lyndon Word 的定义
假如某个字符串 (S) 满足 (|root(S)|=|S|)，且 (S) 严格小于 (S) 的所有循环同构串，那么称 (S) 是一个 Lyndon Word，简记为 LW，并假设所有 LW 构成的集合为 (m{LW})
II. Lyndon Word 的性质
Lyndon Word 与 Border
断言：对于所有 (winm{LW})，均满足：(w) 没有 Border，证明如下：
证：
采用反证法，设某个 LW (w) 中有 Border (u)
不妨设 (w=ux=yu)，那么由于 LW 的性质，(xu>w,uy>w)
又因 (w=yu)，所以 (xu>yu)，所以 (x>y)，同理根据 (uy>ux) 有 (y>x)
显然导出矛盾，故原命题成立
Lyndon Word 与后缀
Lyndon Word 有等价定义：(winm{LW}) 当且仅当 (w) 小于其所有真后缀，证明如下：
证：
假设 (v) 为 (w) 的任意真后缀，且 (w=uv)
证明 (w<vimplies w<vu)
由于 (|w|>|v|)，因此 (wll v)，此时 (wll vu)，故原命题得证
证明 (w<vuimplies w<v)
考虑 (w'=w[1cdots |v|])，显然 (w'le w)，若 (w'=w) 那么 (v) 是 (w) 的一个 Border，与上一个性质矛盾，因此我们知道 (w'<v)，又因为 (|w'|=|v|) 且 (w'ne v)，所以 (w'll v) 所以 (w<v)
综上所述，我们证明了 (w<viff w<vu)，那么我们就证明了原命题等价于 LW 的定义，因此“(w) 小于其所有真后缀”也是 LW 一个等价的定义
Lyndon Word 的标准分解
Lyndon Word 的复合
假设 (u,vinm{LW})，那么 (uvinm{LW}iff u<v)，证明如下：
证：
证明 (uvinm{LW}implies u<v)
根据 LW 的等价定义，(uvll v)，又因为 (u<uv)，因此 (u<v) 得证
证明 (u<vimplies uvinm{LW})
考虑 (uv) 的任意一个真后缀 (s)
(|s|>|v|) 时
假设 (s=u'v)，注意到 (u') 是 (u) 的真后缀，那么我们知道 (u'gg u)，所以我们知道 (u'gg uv) 则 (sgg uv)
(|s|<|v|) 时
此时 (s) 为 (v) 的真后缀，那么 (sgg v)，且 (v>u)，故 (sgg u) 所以 (s>uv)
(|s|=|v|) 时
显然有 (s=v)，即证 (v>uv)
若 (ull v)
此时显然有 (uvll v)
若 (u) 为 (v) 的前缀
记 (v=uv')，即证 (uv'>uv)，事实上我们只需要比较 (v') 和 (v) 的大小即可，注意到 (v') 为 (v) 的一个真后缀且 (v) 为 LW，那么 (v'>v) 成立，所以 (v>uv) 成立
综上所述，(u<vimplies uvinm{LW})
所以我们证明了 (forall u,vin m{LW})，(uvinm{LW}iff u<v)
Lyndon Word 的分解
假设 (winm{LW}) 且 (|w|ge 2)，设 (v) 为 (w) 的最小真后缀，记 (w=uv)，则 (u,v) 满足 (u<v) 且 (u,vinm{LW})，证明如下：
证：
证明 (vinm{LW})
事实上，考虑 (v) 的每个真后缀 (v')，由于 (v') 也是 (w) 的一个真后缀，那么 (v< v') 同样成立，因此 (vinm{LW})
证明 (u<v)
若 (|u|ge |v|)
那么 (w<v) 等价于 (u<v)，此时命题成立
若 (|u|<|v|)
此时由于 (w<v) 那么 (ule v[1cdots |u|])
若 (u< v[1cdots|u|])
由于 (|u|=|v|) 且 (une v)，那么 (ull v[1cdots |u|]) 则 (u<v)
若 (u=v[1cdots |u|])
此时 (u) 是 (v) 前缀同样有 (u<v) 成立
证明 (uin m{LW})
考虑反证法，存在一个 (u) 的真后缀 (u'<u)，那么考虑 (w) 的真后缀 (u'v)
若 (u'll u)
那么一定有 (u'v<uv=w) 与 (w) 是 LW 矛盾
若 (u') 为 (u) 前缀
此时设 (u=u't)，由于 (w) 是 LW，那么应该满足 (u'v>uv)，那么 (u'v>u'tv) 即 (v>tv)，此时出现了一个比 (v) 更小的 (w) 的真后缀，这与假设矛盾
综上，(u) 必须是 LW
综上所述，此时有 (u<v) 且 (u,vinm{LW})
此时我们可以证明 (v) 是 (w) 最大的一个 LW 真后缀，证明如下：
证：
假设存在另一个 (w) 的 LW 真后缀 (v') 满足 (|v'|>v)，那么 (v) 是 (v') 的真后缀，由于 (v'inm{LW})，那么 (v>v') 这与 (v) 是 (w) 的最小真后缀矛盾
而此时我们记 (w=uv) 为 (w) 的标准分解
基于标准分解的 Lyndon Word 定义形式
(winm{LW}) 等价于 (|w|=1) 或 (|w|ge 2) 且存在 (u,vinm{LW}) 满足 (u<v) 且 (w=uv)
证明如下：
证：
当 (|w|=1) 时原命题显然成立，因此只讨论 (|w|ge 2) 的情况，简记该判定条件为“(exists u,v)”
证明 (exists u,vimplies winm{LW})
根据“Lyndon Word 的复合”一节中的结论，我们知道这个结论是成立的
证明 (winm{LW}implies exists u,v)
设 (v) 为 (w) 的最小真后缀，且 (u) 满足 (w=uv)，根据“Lyndon Word的分解”一节中的结论，我们知道此时的 (uv) 就满足条件
综上所述，我们知道 (|w|=1text{ or }exists u,v) 也是一个 LW 的判定方式
III. Lyndon Word 的经典问题
Lyndon Word 的后继问题
假设字符集为 ({1,2,cdots,sigma})，且字符串长度 (le n)，给定满足条件的 LW (S)，求字典序大于 (S) 的最小合法 LW (S')
给出一个构造方法，先将 (S) 不断循环拼接得到一个长度为 (n) 的字符串 (S^star)（最后一个周期可以不是整周期），找到 (S^star) 最后一个不是 (sigma) 的字符 (S^star_k)，并让 (S^star_kgets S^star_k+1)，然后删掉子串 (S^star[k+1cdots n]) 就得到了 (S) 的后继 (S')，证明如下：
证：
证明 (S'inm{LW})
注意到 (S^star[1cdots k]) 一定是一个近似 LW，而让 (S^star_kgets S^star_k+1)，我们就得到了一个 LW，有关“近似 LW”的内容以及相关证明请参看后文“Duval 算法求 Lyndon 分解”一章中的“引理”部分和“算法流程”部分的第二种情况，会给出一个严谨的证明
证明不存在 (Tinm{LW}) 满足 (S<T<S')
根据定义，比较 (T,S')，假设 (i) 表示满足 (T_i<S'_i) 的最小 (i)，显然 (T[1cdots |S|]=S) 所以 (ige |S|)
假设 (ktimes|S|<ile (k+1)times |S|)，且 (i-ktimes|S|=rin[1,|S|])
若 (i<|S'|)
考虑 (T) 的真后缀 (T[ktimes |S|+1cdots |T|])
根据假设，(S’[ktimes|S|+1cdots i-1]=T[ktimes |S|+1cdots i-1])
由于 (S') 的构造定理，(S'[ktimes |S|+1cdots i-1]=S[1cdots r-1]=T[1cdots r-1])
因此，我们如果要比较 (T) 与 (T[ktimes |S|+1cdots |T|]) 的大小关系，只需比较 (T_i) 与 (T_{r}) 的大小
注意到 (T_i<S'_i=S_r<T_r)，因此 (T[ktimes |S|+1cdots |T|]<T)
与 (Tinm{LW}) 矛盾，故这种情况不存在
若 (i=|S'|)
根据对 (S') 的定义，我们知道 (ktimes |S|<|S'|le (k+1)times |S|)，所以 (|T|le (k+1)times S)
根据定义，此时必然有 (T_i=S'_i-1=S_{r})，同样考虑 (T) 的真后缀 (T[ktimes |S|+1cdots |T|])
注意到 (T[i+1cdots |T|]le sigma^{|T|-i}) 且 (T[r+1cdots |S|]=S[r+1cdots |S|]=sigma^{|S|-r})，因此 (T[i+1cdots |T|]le S[r+1cdots |S|])
又因为 (T[ktimes |S|+1cdots |T|]>T)，这就要求 (T[ktimes|S|+1cdots i]gg T[1cdots r])，又因为事实上 (T[ktimes |S|+1cdots i]=T[1cdots r])，这就导出了矛盾
综上，我们证明了 (S') 是 (S) 在 (m{LW}) 中的后继
Lyndon Word 的计数问题
设字符串长度恰好为 (n)，字符集大小为 (m)，统计所有这样的字符串中 LW 的数量
首先考虑 (Sinm{LW}) 的判定条件：
- (|root(S)|=|S|)
- (S) 小于 (S) 的所有循环同构串
先考虑第二个问题，假如我们不保证 (|root(S)|=|S|)，那么我们可以考虑对“(S) 小于等于 (S) 的所有循环同构串”的 (S) 进行计数，然后再在这些串中统计 (|root(S)|=|S|) 的即可
为了解决第一个问题，我们可以这样想：把每个 (S) 都到环上，即变成圆排列的形式，那么一个圆排列中的满足条件的 (S) 有且仅有一个，所以我们只需要求长度为 (n)，值域为 (m) 的有旋转无翻转圆排列计数即可，记这个问题的答案为 (S_n)
接下来考虑第二个问题：在 (S_n) 个圆排列中，只有那些最小整周期为 (n) 的才能转化成一个 LW，因此我们记：在 (S_n) 个圆排列中，最小整周期恰好为 (n) 的圆排列的个数为 (T_n)
容易证明 (T_n) 就是我们要求的答案
首先考虑如何根据 (T_n) 推导出 (S_n)，显然对于一个最小整周期为 (d) 且 (dmid n) 的长度为 (d) 的圆排列 (T)，我们构造 (S=underbrace{TTcdots T}_{n/dtext{ times}}=T^{n/d})，显然这样的 (S) 与 (T) 之间存在双射，即我们可以证明对于 (T) 进行旋转后得到 (T')，则 (S'=(T')^{n/d}) 与 (S) 是循环同构的
因此我们知道对于所有长度为 (n)，最小整周期为 (d) 的圆排列，其总数恰好为 (T_d)，因此我们得到如下的公式：
注意到这个式子实际上等价于 (S=T*1)，其中 (S(n)=S_n,T(n)=T_n,1(n)=1)，(*) 为狄利克雷卷积符号
那么根据莫比乌斯反演，我们能够得到 (T=S*mu)，即：
因此问题转化为求 (S_d) 的值，而求 (S) 事实上是一个经典的项链计数问题，在《具体数学》第四章有如下的解法：
解：
对于 (S_n) 个本质不同圆排列，我们任意写出其对应的一个字符串，对于每个字符串，再写出其 (n) 个循环同构串，构成一个可重集 (m A)，显然 (|m A|=ntimes S_n)，对 (|m A|) 进行 Double-Couting，考虑每个字符串 (S=S_1S_2S_3cdots S_{n}) 出现的次数，根据循环同构的定义得到：
[|m A|=sum_Ssum_{i=1}^{n}[S_1S_2cdots S_{n}=S_iS_{i+1}cdots S_{n}S_1cdots S_{i-1}] ]交换求和号，转化为统计贡献的形式：
[|m A|=sum_{i=1}^{n}sum_S[S_1S_2cdots S_{n}=S_iS_{i+1}cdots S_{n}S_1cdots S_{i-1}] ]注意到对于给定的 (i)，满足条件的 (S) 当且仅当 (S) 有一个大小为 (i) 的约数的整周期，事实上，根据整周期的性质，这等价于 (S) 有整周期 (gcd(n,i))
根据整周期的性质，有整周期 (gcd(n,i)) 的 (S) 的数量等价于长度为 (gcd(n,i)) 的任意字符串的数量，即 (m^{gcd(n,i)}) 种
所以可以优化掉第二个求和号，再根据 (gcd(n,i)) 的性质对于不同的 (d=gcd(n,i)) 统计对应 (i) 的数量，不难得到如下变形过程：
[|m A|=sum_{i=1}^{n} m^{gcd(n,i)}=sum_{dmid n}varphileft(dfrac ndright)times m^d ]运用 (|m A|=ntimes S_n) 的事实得到 (S_n=dfrac 1nsum_{d|n}varphileft(tfrac ndright)times m^d)
所以我们得到了 (S_n) 的一个简洁表达，据此计算 (T_n) 即可，不过事实上，(T_n) 也有更加优美的形式，具体分析如下：
解：
记 (id(n)=n)，根据狄利克雷卷积和莫比乌斯反演的基本推论有 (id=varphi*1implies varphi=id*mu)
注意到 (S=T*1)，且 (nS=n(T*1))，我们记一个新的函数 (T'(n)=nT_n)，注意这里的两个 (n) 都是自变量而非常数，考虑构造函数 (id*T')，根据狄利克雷卷积定义进行展开：
[begin{aligned} id*T'(n) &=sum_{dmid n}idleft(dfrac ndright)times T'(d)\ &=sum_{dmid n}dfrac ndtimes(dtimes T_n)\ &=nsum_{dmid n} T_n\ &=ntimes(T*1(n)) end{aligned} ]因此 (id*T'=n(T*1))，故 (ntimes S_n=id*T')
此时结合 (nS=varphi* m^n(n)) 运用莫比乌斯反演得到：(id*T'=nS=varphi *m^n(n)=id*mu*m^n(n))
因此 (T'=mu*m^n(n))
综上所述，我们得到 (T_n=dfrac 1nsum_{dmid n}muleft(dfrac ndright)times m^d)
IV. 习题演练
[CSES2209] - Counting Necklaces
项链计数模板，求 (S_n) 的值即可，可以用线性筛预处理 (varphi(n)) 的值
时间复杂度 (Theta(n+sqrt nlog n))
#include<bits/stdc++.h> #define int long long using namespace std; const int MAXN=1e6+1,MOD=1e9+7; int n,m,phi[MAXN]; bool mark[MAXN]; vector <int> primes; inline int ksm(int a,int b,int m=MOD) { int ret=1; while(b) { if(b&1) ret=a*ret%MOD; a=a*a%MOD; b=b>>1; } return ret; } inline int calc(int d) { return ksm(m,d)*phi[n/d]%MOD; } signed main() { int ans=0; scanf("%lld%lld",&n,&m); phi[1]=1; for(int i=2;i<=n;++i) { if(!mark[i]) phi[i]=i-1,primes.push_back(i); for(int p:primes) { if(p*i>n) break; mark[p*i]=true,phi[p*i]=(i%p==0)?(phi[i]*p):(phi[i]*(p-1)); if(i%p==0) break; } } for(int i=1;i*i<=n;++i) { if(n%i!=0) continue; ans=(ans+calc(i))%MOD; if(i*i!=n) ans=(ans+calc(n/i))%MOD; } printf("%lldn",ans*ksm(n,MOD-2)%MOD); return 0; } [CSES2210] - Counting Grids
类似上一个问题，记答案为 (S_n)，对于一个染色的 (ntimes n) 网格，将其旋转四次后做 Double-Counting，考虑每个网格在旋转多少度后重复出现了多少次
如上图，根据旋转网格的性质我们可以把一个网格划分成 (4) 块，分别是 (A,B,C,D)，不难发现每次旋转后只会交换 (A,B,C,D) 的相对顺序，并不会改变 (A,B,C,D) 的块内心态，记每块的大小为 (m)，对 (n) 的奇偶性分别讨论：
-
(n) 为奇数时
此时 (m=dfrac{n^2-1}4)
-
某个网格在旋转 (0^circ) 时出现过
任何的网格都符合这样的要求，这样的网格共有 (2^{ntimes n}) 个
-
某个网格在旋转 (180^circ) 时出现过
这要求 (A=B,C=D)，而中间的那个位置可以随便取色，这样的网格共有 (2times 2^mtimes 2^m=2^{2times m+1})
-
某个网格在旋转 (90^circ) 或 (270^circ) 时出现过
这要求 (A=B=C=D)，而中间那个位置依然可以随便取色，这样的网格共有 (2times 2^m=2^{m+1}) 个
综上，我们得到 (4times S_n=2^{ntimes n}+2^{m+1}+2^{2times m+1}+2^{m+1})，当 (n>1) 时，(S_n=2^{ntimes n-2}+2^{2times m-1}+2^m)，当 (n=1) 时 (S_n=2)
-
-
(n) 为偶数时
此时 (m=dfrac{n^2}4)
-
某个网格在旋转 (0^circ) 时出现过
任何的网格都符合这样的要求，这样的网格共有 (2^{ntimes n}) 个
-
某个网格在旋转 (180^circ) 时出现过
这要求 (A=B,C=D)，这样的网格共有 (2^mtimes 2^m=2^{2times m})
-
某个网格在旋转 (90^circ) 或 (270^circ) 时出现过
这要求 (A=B=C=D)，而中间那个位置依然可以随便取色，这样的网格共有 (2^m) 个
综上，我们得到 (4times S_n=2^{ntimes n}+2^{m}+2^{2times m}+2^m)，则 (S_n=2^{ntimes n-2}+2^{2times m-2}+2^{m-1})
-
综上所述，我们得到 (S_n) 的表达式：
快速幂计算即可
时间复杂度 (Theta(log n))
#include<bits/stdc++.h> #define int long long using namespace std; const int MOD=1e9+7; inline int ksm(int a,int b,int m=MOD) { int ret=1; while(b) { if(b&1) ret=a*ret%MOD; a=a*a%MOD; b=b>>1; } return ret; } signed main() { int n; scanf("%lld",&n); int m=(n%2==1)?((n*n-1)/4):(n*n/4); if(n==1) puts("2"); else if(n%2==1) printf("%lldn",(ksm(2,n*n-2)+ksm(2,2*m-1)+ksm(2,m))%MOD); else printf("%lldn",(ksm(2,n*n-2)+ksm(2,2*m-2)+ksm(2,m-1))%MOD); return 0; } [BZOJ1361] - [WC2004]孪生项链
根据“Lyndon Word”的经典问题一节中介绍的公式计算即可，注意第一问要写高精度
时间复杂度 (Theta(ksqrt k+n))，其中 (Theta(ksqrt k)) 的 (Theta(sqrt k)) 是枚举因子数量 (Theta(k)) 是高精度复杂度
#include<bits/stdc++.h> using namespace std; const int MAXN=1001; struct BigInt { vector <int> dig; BigInt() { dig.clear(); } BigInt(vector <int> _dig) { dig=_dig; } BigInt(int x) { while(x) dig.push_back(x%10),x/=10; } inline int& operator [](int x) { return dig[x]; } inline int length() { return (int)dig.size(); } inline void update() { while(!dig.empty()&&dig.back()==0) dig.pop_back(); } inline friend BigInt operator +(BigInt &A,BigInt &B) { BigInt C(vector<int>(max(A.length(),B.length())+1,0)); for(int i=0;i<A.length();++i) C[i]+=A[i]; for(int i=0;i<B.length();++i) C[i]+=B[i]; for(int i=0;i<C.length()-1;++i) C[i+1]+=C[i]/10,C[i]%=10; C.update(); return C; } inline friend BigInt operator -(BigInt &A,BigInt &B) { BigInt C(vector<int>(max(A.length(),B.length())+1,0)); for(int i=0;i<A.length();++i) C[i]+=A[i]; for(int i=0;i<B.length();++i) C[i]-=B[i]; for(int i=0;i<C.length()-1;++i) while(C[i]<0) --C[i+1],C[i]+=10; C.update(); return C; } inline friend BigInt operator /(BigInt &A,const int &d) { BigInt B(vector<int>(A.length(),0)); for(int i=A.length()-1,r=0;i>=0;--i) r=r*10+A[i],B[i]=r/d,r%=d; B.update(); return B; } inline void print() { for(int i=(int)dig.size()-1;i>=0;--i) printf("%d",dig[i]); puts(""); } } pw[MAXN]; int mu[MAXN]; bool mark[MAXN]; vector <int> primes; signed main() { int n,m,k; string S; cin>>n>>m>>k>>S; //task 1 pw[0]=BigInt(1); for(int i=1;i<=k;++i) mu[i]=1,pw[i]=pw[i-1]+pw[i-1]; for(int i=2;i<=k;++i) { if(!mark[i]) mu[i]=-1,primes.push_back(i); for(int p:primes) { if(p*i>k) break; mark[p*i]=true,mu[p*i]=(i%p==0)?0:(-mu[i]); if(i%p==0) break; } } BigInt ans(0); for(int i=1;i*i<=k;++i) { if(k%i!=0) continue; if(mu[i]==1) ans=ans+pw[k/i]; if(i*i!=k&&mu[k/i]==1) ans=ans+pw[i]; } for(int i=1;i*i<=k;++i) { if(k%i!=0) continue; if(mu[i]==-1) ans=ans-pw[k/i]; if(i*i!=k&&mu[k/i]==-1) ans=ans-pw[i]; } ans=ans/k; ans.print(); //task 2 string T; while((int)T.length()<n) T=T+S; T.resize(n); while(!T.empty()&&T.back()=='1') T.pop_back(); assert(!T.empty()); T[(int)T.length()-1]='1'; cout<<T<<"n"; return 0; } [CodeForcesGym - 100162G] - Lyndon Words
从 (texttt{a}) 开始每次暴力找后缀就行，注意实现常数，比如不要用 STL string 类，最好自己手写一个字符数组维护一下尾指针就行
#include<bits/stdc++.h> using namespace std; const int MAXN=31; char ch[MAXN]; signed main() { int n,m,l,r,T=0; while(scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF) { char sigma=m-1+'a'; printf("Case %d:n",++T); int tail=0; ch[++tail]='a'; for(int id=1;id<=r;++id) { if(l<=id) { for(int i=1;i<=tail;++i) putchar(ch[i]); putchar('n'); } int cyc=tail; while(tail<n) { ++tail; ch[tail]=ch[tail-cyc]; } while(ch[tail]==sigma) --tail; ++ch[tail]; } } } 二、Lyndon 分解
I. Lyndon 分解定理
Lyndon 分解的定义
首先定义对于任意字符串 (S) 的一个 Lyndon 分解：
Lyndon 分解指的是一个字符串序列 (w={w_1,w_2,w_3,cdots,w_k})，满足 (S=w_1w_2w_3cdots w_k)，其中 (w_iinm{LW})，且 (w_1ge w_2ge w_3gecdotsge w_k)
Lyndon 分解定理
Lyndon 分解定理告诉我们，对于任意字符串 (S)，其 Lyndon 分解存在且唯一
Lyndon 分解的存在性
首先我们把 (S) 写成 (S=S_1S_2S_3cdots S_{|S|})，此时我们就把 (S) 写成了 (|S|) 个 LW 的形式
此时对于任意两个相邻的 LW (w_i,w_{i+1})，若 (w_i<w_{i+1}) 我们就把 (w_i,w_i+1) 合并成 (w_iw_{i+1}) 不断重复这个过程直到这样的 (w_i,w_{i+1}) 不存在为止，可以证明这个过程一定会停止，那么我们就得到了一个 Lyndon 分解
Lyndon 分解的唯一性
假设 (S) 存在两个不同的 Lyndon 分解 (w_1sim w_k) 与 (w'_1sim w'_{k'})
如下图，假设 (w_i) 与 (w'_i) 是这两个分解第一个不同的地方，且 (|w_i|>|w'_i|)，我们设 (|w'_iw'_{i+1}cdots w'_{i+j}|ge w_i)，且 (|w'_iw'_{i+1}cdots w'_{i+j-1}|< w_i)，显然 (jge 1)，(T) 为 (w_i) 与 (w'_{i+j}) 的交
根据 (w') 是一个 Lyndon 分解的假设，我们得到 (Tle w'_{i+j}le w'_{i+j-1}lecdotsle w'_ile w_i)，又因为 (T) 是 (w_i) 的一个真后缀，那么 (Tle w_i) 与 (w_i) 是 LW 的要求矛盾，因此这样的 Lyndon 分解必须是唯一的
II. Lyndon 分解的性质
定义 (w={w_1,w_2cdots ,w_k}) 为 (S) 的 Lyndon 分解，我们有如下的性质：
Lyndon 分解与最小后缀
(w_k) 为 (S) 的最小后缀，证明如下：
证：
对于长度小于 (|w_k|) 的后缀，根据 (w_k) 是 LW 的事实即可得到所有长度小于 (|w_k|) 的后缀字典序一定大于 (w_k)
而对于任意长度大于 (|w_k|) 的后缀 (S')，我们设 (S'=w'_iw_{i+1}w_{i+2}cdots w_k)，其中 (w'_i) 是 (w_i) 的一个后缀，那么根据 Lyndon 分解的定义，(w_kle w_{k-1}lecdots le w_i)，且由于 (w'_i) 是 LW (w_i) 的一个后缀，我们知道 (w'_ile w_i)，因此 (w_kle w'_i) 又因 (|S'|>|w_k|)，所以 (S'>w_k)
综上，(w_k) 为 (S) 的最小后缀
Lyndon 分解与最长 LW 后缀
(w_k) 为 (S) 最大的 LW 后缀，证明如下：
证：
对于任意长度大于 (|w_k|) 的后缀 (S')，我们设 (S'=w'_iw_{i+1}w_{i+2}cdots w_k)，其中 (w'_i) 是 (w_i) 的一个后缀，同上面的分析，(S'>w_k)，那么 (S') 必然不可能是 LW
Lyndon 分解与最长 LW 前缀
(w_1) 为 (S) 最大的 LW 前缀，证明如下：
证：
对于任意长度大于 (|w_1|) 的前缀 (S')，我们设 (S'=w_1w_2cdots w'_i)，其中 (w'_i) 为 (w_i) 的一个前缀，类似上面的过程，我们得到 (w'_ile w_ile w_{i-1}lecdots le w_1)，且 (|w'_i|<|S'|)，因此 (w'_i<S')，那么 (S') 必然不可能是 LW
III. Duval 算法求 Lyndon 分解
介绍
Duval 算法是一种支持在 (Theta(|S|)) 时间内求出 (S) 的 Lyndon 分解的算法
引理
我们定义字符串 (w') 为“近似LW”当且仅当存在 (winm{LW}) 使得 (w') 为 (w) 的一个前缀
那么我们有如下的引理：若 (w’) 为一个近似 LW，其中 (t c) 为 (w') 的最后一个字符，如果把 (t c) 修改成一个更大的字符 (t d) ，那么新的 (w') 为一个 LW
证：
不妨设 (w'u) 为一个 LW，那么考虑 (w') 的一个真后缀 (v)，记 (w=v'v)，那么根据 (w'u) 为 LW，我们知道 (vu>w'u)，且 (|v|<|w'|)，考虑 (v) 和 (w'[1cdots |v|]) 的大小关系，显然 (vge w'[1cdots |v|])
那么此时考虑增大 (w') 的末尾，那么 (v) 的末尾会增大且 (w'[1cdots |v|]) 的末尾不会增大，因此 (v> w'[1cdots|v|])，由于 (vne w'[1cdots |v|])，所以 (vgg w'[1cdots |v|]) 所以 (v>w')，故修改后的 (w') 是一个 LW
维护内容
如下图，在 Duval 算法的过程中，我们将整个字符串 (S) 分成了三个部分，并且维护了一些变量：
- (S_1)：已经扫描并处理完成的串
- (w_1sim w_g)：一些满足 (w_1ge w_2ge cdotsge w_g) 且 (S_1=w_1w_2cdots w_g) 的一些 LW
- (i)：(S_1) 的尾指针，满足 (S_1=S[1cdots i-1])，(S_2) 的头指针
- (S_2)：已经扫描但尚未处理完成的串
- (t_1sim t_h)：一些满足 (t_1=t_2=cdots =t_h) 的 LW，且 (w_g>t_h)
- (t')：(S_2) 拆分后剩下的一个近似 LW 串，满足 (t') 是 (t_h) 的某个前缀
- (j)：维护 (t') 与 (t_h) 的匹配长度
- (k)：(S_2) 的尾指针，满足 (S_2=S[icdots k-1])，(t') 的尾指针，满足 (|t_h|=k-j)，(S_3) 的头指针
- (S_3)：未扫描的串
算法流程
考虑每次将 (k) 右移一位，并且讨论 (S_j) 和 (S_k) 的大小关系
- (S_j=S_k)，(t') 与 (t_h) 继续匹配即可 (jgets j+1,kgets k+1)
- (S_j<S_k)，此时根据引理可以知道新的 (t') 会变成一个 LW 满足 (t'>t_h)，那么根据“Lyndon Word 的复合”一节中的结论，(t_ht') 也是一个 LW，那么由于 (t_ht'>t_h=t_{h-1}) 继续重复不断使用该结论即可证明 (t_1t_2cdots t_ht') 为 LW，因此设整个 (t_1t_2cdots t_ht') 为新的 (t_1)，即 (jgets i,kgets k+1)
- (S_j>S_k)，失配了，此时把 (t_1sim t_h) 变成 (w_{g+1}sim w_{g+h})，后面新生成的 Lyndon 串也不会超过 (w_{g+h}=t_h)，并且此时重新匹配 (k)，记 (S_t) 为 (t') 的第一个字符，即 (igets t,jgets t,kgets i+1)
复杂度分析
注意到只有 (k) 会回退，而 (i) 每次都是增加的且每次回退 (k) 事实上也不减小 (i+k) 的值，均摊分析可以证明 Duval 算法的复杂度是 (Theta(|S|)) 的
代码实现
根据上面的流程，我们能够写出如下伪代码（记 (n=|S|)）：
i=1 while i<=n: j=i,k=i+1 while k<=n and S[j]<=S[k]: if S[j]=S[k]: j=j+1,k+k+1 else: j=i,k=k+1 while i<=j: print(S[i...(i+k-j+1)]) i=i+k-j IV. Lyndon 分解与最小表示
最小表示定义为一个字符串 (S) 的所有循环同构串（含自身）中字典序最小的一个
我们有如下的结论：对 (S^2) 进行 Lyndon 分解，设 (w_i) 对应子串 (S^2[l_icdots r_i])，那么找到满足 (l_ile |S|< r_i) 的 (i) 则 (S^2[l_icdots l_i+n-1]) 即为 (S) 的最小表示，证明如下：
证：
对于任意循环同构串 (S^2[lcdots r]ne S^2[l_icdots l_i+n-1])，由于 (|S^2[lcdots r]|=r-l+1=S)，那么 (rle |S|le r_i) 总是成立，假设 (S^2[lcdots r]=w'_jw_{j+1}cdots)，其中 (w'_j) 为 (w_j) 的一个后缀，且我们知道 (ile j)，那么我们有 (w'_j>w_j>w_{j+1}>cdots >w_i)，这就证明了 (S^2[lcdots r]<S[l_icdots l_i+n-1])
V. 习题演练
[洛谷6114] - 【模板】Lyndon 分解
模板题，直接用 Duval 算法求 Lyndon 分解即可
时间复杂度 (Theta(|s|))
#include<bits/stdc++.h> using namespace std; const int MAXN=5e6+5; char s[MAXN]; signed main() { scanf("%s",s+1); int n=strlen(s+1),ans=0; for(int i=1;i<=n;) { int j=i,k=i+1; while(k<=n&&s[j]<=s[k]) j=(s[j]==s[k])?(j+1):i,++k; while(i<=j) ans^=(i+k-j-1),i+=k-j; } printf("%dn",ans); return 0; } [洛谷1368] - 【模板】最小表示法
模板题，根据我们上面的分析，先用 Duval 算法求出 ({a_i}^2) 的 Lyndon 分解，然后找到满足条件的 (w_i) 即可
时间复杂度 (Theta(n))
#include<bits/stdc++.h> using namespace std; struct node { int l,r; node() { l=r=0; } node(int _l,int _r) { l=_l,r=_r; } }; const int MAXN=1e6+1; int S[MAXN]; signed main() { vector <node> w; int n; scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&S[i]),S[i+n]=S[i]; int m=n<<1; for(int i=1;i<=m;) { int j=i,k=i+1; while(k<=m&&S[j]<=S[k]) j=(S[j]==S[k])?(j+1):i,++k; while(i<=j) w.push_back(node(i,i+(k-j)-1)),i+=k-j; } for(auto x:w) { if(x.l<=n&&n<x.r) { for(int i=x.l;i<x.l+n;++i) printf("%d ",S[i]); puts(""); break; } } return 0; } 
