By DaiRuiChen007

• 对于两个字符串 S,T，用 ST 表示将 T 接在 S 后面得到的字符串（即 S+T）
• 对于两个字符串 S,T，若 S 的字典序严格小于 T 的字典序则即 S<T，若在满足 S<T 的前提下满足 S 不是 T 的前缀，我们记 S≪T，同理能够得到 S>T 和 S≫T 的定义

一、Lydon Word

I. Lyndon Word 的定义

假如某个字符串 S 满足 |root(S)|=|S|，且 S 严格小于 S 的所有循环同构串，那么称 S 是一个 Lyndon Word，简记为 LW，并假设所有 LW 构成的集合为 LW

II. Lyndon Word 的性质

Lyndon Word 与 Border

断言：对于所有 w∈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 有等价定义：w∈LW 当且仅当 w 小于其所有真后缀，证明如下：

假设 v 为 w 的任意真后缀，且 w=uv

• 证明 w<v⟹w<vu

  由于 |w|>|v|，因此 w≪v，此时 w≪vu，故原命题得证

• 证明 w<vu⟹w<v

  考虑 w′=w[1⋯|v|]，显然 w′≤w，若 w′=w 那么 v 是 w 的一个 Border，与上一个性质矛盾，因此我们知道 w′<v，又因为 |w′|=|v| 且 w′≠v，所以 w′≪v 所以 w<v

综上所述，我们证明了 w<v⟺w<vu，那么我们就证明了原命题等价于 LW 的定义，因此“w 小于其所有真后缀”也是 LW 一个等价的定义

Lyndon Word 的标准分解

Lyndon Word 的复合

假设 u,v∈LW，那么 uv∈LW⟺u<v，证明如下：

• 证明 uv∈LW⟹u<v

  根据 LW 的等价定义，uv≪v，又因为 u<uv，因此 u<v 得证

• 证明 u<v⟹uv∈LW

  考虑 uv 的任意一个真后缀 s

  • |s|>|v| 时

    假设 s=u′v，注意到 u′ 是 u 的真后缀，那么我们知道 u′≫u，所以我们知道 u′≫uv 则 s≫uv

  • |s|<|v| 时

    此时 s 为 v 的真后缀，那么 s≫v，且 v>u，故 s≫u 所以 s>uv

  • |s|=|v| 时

    显然有 s=v，即证 v>uv

    • 若 u≪v

      此时显然有 uv≪v

    • 若 u 为 v 的前缀

      记 v=uv′，即证 uv′>uv，事实上我们只需要比较 v′ 和 v 的大小即可，注意到 v′ 为 v 的一个真后缀且 v 为 LW，那么 v′>v 成立，所以 v>uv 成立

  综上所述，u<v⟹uv∈LW

所以我们证明了 ∀u,v∈LW，uv∈LW⟺u<v

Lyndon Word 的分解

假设 w∈LW 且 |w|≥2，设 v 为 w 的最小真后缀，记 w=uv，则 u,v 满足 u<v 且 u,v∈LW，证明如下：

• 证明 v∈LW

  事实上，考虑 v 的每个真后缀 v′，由于 v′ 也是 w 的一个真后缀，那么 v<v′ 同样成立，因此 v∈LW

• 证明 u<v

  • 若 |u|≥|v|

    那么 w<v 等价于 u<v，此时命题成立

  • 若 |u|<|v|

    此时由于 w<v 那么 u≤v[1⋯|u|]

    • 若 u<v[1⋯|u|]

      由于 |u|=|v| 且 u≠v，那么 u≪v[1⋯|u|] 则 u<v

    • 若 u=v[1⋯|u|]

      此时 u 是 v 前缀同样有 u<v 成立

• 证明 u∈LW

  考虑反证法，存在一个 u 的真后缀 u′<u，那么考虑 w 的真后缀 u′v

  • 若 u′≪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,v∈LW

此时我们可以证明 v 是 w 最大的一个 LW 真后缀，证明如下：

假设存在另一个 w 的 LW 真后缀 v′ 满足 |v′|>v，那么 v 是 v′ 的真后缀，由于 v′∈LW，那么 v>v′ 这与 v 是 w 的最小真后缀矛盾

而此时我们记 w=uv 为 w 的标准分解

基于标准分解的 Lyndon Word 定义形式

w∈LW 等价于 |w|=1 或 |w|≥2 且存在 u,v∈LW 满足 u<v 且 w=uv

证明如下：

当 |w|=1 时原命题显然成立，因此只讨论 |w|≥2 的情况，简记该判定条件为“∃u,v”

• 证明 ∃u,v⟹w∈LW

  根据“Lyndon Word 的复合”一节中的结论，我们知道这个结论是成立的

• 证明 w∈LW⟹∃u,v

  设 v 为 w 的最小真后缀，且 u 满足 w=uv，根据“Lyndon Word的分解”一节中的结论，我们知道此时的 uv 就满足条件

综上所述，我们知道 |w|=1 or ∃u,v 也是一个 LW 的判定方式

III. Lyndon Word 的经典问题

Lyndon Word 的后继问题

假设字符集为 {1,2,⋯,σ}，且字符串长度 ≤n，给定满足条件的 LW S，求字典序大于 S 的最小合法 LW S′

给出一个构造方法，先将 S 不断循环拼接得到一个长度为 n 的字符串 S⋆（最后一个周期可以不是整周期），找到 S⋆ 最后一个不是 σ 的字符 Sk⋆，并让 Sk⋆←Sk⋆+1，然后删掉子串 S⋆[k+1⋯n] 就得到了 S 的后继 S′，证明如下：

• 证明 S′∈LW

  注意到 S⋆[1⋯k] 一定是一个近似 LW，而让 Sk⋆←Sk⋆+1，我们就得到了一个 LW，有关“近似 LW”的内容以及相关证明请参看后文“Duval 算法求 Lyndon 分解”一章中的“引理”部分和“算法流程”部分的第二种情况，会给出一个严谨的证明

• 证明不存在 T∈LW 满足 S<T<S′

  根据定义，比较 T,S′，假设 i 表示满足 Ti<Si′ 的最小 i，显然 T[1⋯|S|]=S 所以 i≥|S|

  假设 k×|S|<i≤(k+1)×|S|，且 i−k×|S|=r∈[1,|S|]

  • 若 i<|S′|

    考虑 T 的真后缀 T[k×|S|+1⋯|T|]

    根据假设，S′[k×|S|+1⋯i−1]=T[k×|S|+1⋯i−1]

    由于 S′ 的构造定理，S′[k×|S|+1⋯i−1]=S[1⋯r−1]=T[1⋯r−1]

    因此，我们如果要比较 T 与 T[k×|S|+1⋯|T|] 的大小关系，只需比较 Ti 与 Tr 的大小

    注意到 Ti<Si′=Sr<Tr，因此 T[k×|S|+1⋯|T|]<T

    与 T∈LW 矛盾，故这种情况不存在

  • 若 i=|S′|

    根据对 S′ 的定义，我们知道 k×|S|<|S′|≤(k+1)×|S|，所以 |T|≤(k+1)×S

    根据定义，此时必然有 Ti=Si′−1=Sr，同样考虑 T 的真后缀 T[k×|S|+1⋯|T|]

    注意到 T[i+1⋯|T|]≤σ|T|−i 且 T[r+1⋯|S|]=S[r+1⋯|S|]=σ|S|−r，因此 T[i+1⋯|T|]≤S[r+1⋯|S|]

    又因为 T[k×|S|+1⋯|T|]>T，这就要求 T[k×|S|+1⋯i]≫T[1⋯r]，又因为事实上 T[k×|S|+1⋯i]=T[1⋯r]，这就导出了矛盾

综上，我们证明了 S′ 是 S 在 LW 中的后继

Lyndon Word 的计数问题

设字符串长度恰好为 n，字符集大小为 m，统计所有这样的字符串中 LW 的数量

首先考虑 S∈LW 的判定条件：

• |root(S)|=|S|
• S 小于 S 的所有循环同构串

先考虑第二个问题，假如我们不保证 |root(S)|=|S|，那么我们可以考虑对“S 小于等于 S 的所有循环同构串”的 S 进行计数，然后再在这些串中统计 |root(S)|=|S| 的即可

为了解决第一个问题，我们可以这样想：把每个 S 都到环上，即变成圆排列的形式，那么一个圆排列中的满足条件的 S 有且仅有一个，所以我们只需要求长度为 n，值域为 m 的有旋转无翻转圆排列计数即可，记这个问题的答案为 Sn

接下来考虑第二个问题：在 Sn 个圆排列中，只有那些最小整周期为 n 的才能转化成一个 LW，因此我们记：在 Sn 个圆排列中，最小整周期恰好为 n 的圆排列的个数为 Tn

容易证明 Tn 就是我们要求的答案

首先考虑如何根据 Tn 推导出 Sn，显然对于一个最小整周期为 d 且 d∣n 的长度为 d 的圆排列 T，我们构造 S=TT⋯T⏟n/d times=Tn/d，显然这样的 S 与 T 之间存在双射，即我们可以证明对于 T 进行旋转后得到 T′，则 S′=(T′)n/d 与 S 是循环同构的

因此我们知道对于所有长度为 n，最小整周期为 d 的圆排列，其总数恰好为 Td，因此我们得到如下的公式：

注意到这个式子实际上等价于 S=T∗1，其中 S(n)=Sn,T(n)=Tn,1(n)=1，∗ 为狄利克雷卷积符号

那么根据莫比乌斯反演，我们能够得到 T=S∗μ，即：

因此问题转化为求 Sd 的值，而求 S 事实上是一个经典的项链计数问题，在《具体数学》第四章有如下的解法：

对于 Sn 个本质不同圆排列，我们任意写出其对应的一个字符串，对于每个字符串，再写出其 n 个循环同构串，构成一个可重集 A，显然 |A|=n×Sn，对 |A| 进行 Double-Couting，考虑每个字符串 S=S1S2S3⋯Sn 出现的次数，根据循环同构的定义得到：

|A|=∑S∑i=1n[S1S2⋯Sn=SiSi+1⋯SnS1⋯Si−1]

交换求和号，转化为统计贡献的形式：

|A|=∑i=1n∑S[S1S2⋯Sn=SiSi+1⋯SnS1⋯Si−1]

注意到对于给定的 i，满足条件的 S 当且仅当 S 有一个大小为 i 的约数的整周期，事实上，根据整周期的性质，这等价于 S 有整周期 gcd(n,i)

根据整周期的性质，有整周期 gcd(n,i) 的 S 的数量等价于长度为 gcd(n,i) 的任意字符串的数量，即 mgcd(n,i) 种

所以可以优化掉第二个求和号，再根据 gcd(n,i) 的性质对于不同的 d=gcd(n,i) 统计对应 i 的数量，不难得到如下变形过程：

|A|=∑i=1nmgcd(n,i)=∑d∣nφ(nd)×md

运用 |A|=n×Sn 的事实得到 Sn=1n∑d|nφ(nd)×md

所以我们得到了 Sn 的一个简洁表达，据此计算 Tn 即可，不过事实上，Tn 也有更加优美的形式，具体分析如下：

记 id(n)=n，根据狄利克雷卷积和莫比乌斯反演的基本推论有 id=φ∗1⟹φ=id∗μ

注意到 S=T∗1，且 nS=n(T∗1)，我们记一个新的函数 T′(n)=nTn，注意这里的两个 n 都是自变量而非常数，考虑构造函数 id∗T′，根据狄利克雷卷积定义进行展开：

id∗T′(n)=∑d∣nid(nd)×T′(d)=∑d∣nnd×(d×Tn)=n∑d∣nTn=n×(T∗1(n))

因此 id∗T′=n(T∗1)，故 n×Sn=id∗T′

此时结合 nS=φ∗mn(n) 运用莫比乌斯反演得到：id∗T′=nS=φ∗mn(n)=id∗μ∗mn(n)

因此 T′=μ∗mn(n)

综上所述，我们得到 Tn=1n∑d∣nμ(nd)×md

IV. 习题演练

[CSES2209] - Counting Necklaces

Problem Link

项链计数模板，求 Sn 的值即可，可以用线性筛预处理 φ(n) 的值

时间复杂度 Θ(n+nlog⁡n)

#include<bits/stdc++.h>#define int long longusing 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("%lld\n",ans*ksm(n,MOD-2)%MOD); return 0;}

[CSES2210] - Counting Grids

Problem Link

类似上一个问题，记答案为 Sn，对于一个染色的 n×n 网格，将其旋转四次后做 Double-Counting，考虑每个网格在旋转多少度后重复出现了多少次

如上图，根据旋转网格的性质我们可以把一个网格划分成 4 块，分别是 A,B,C,D，不难发现每次旋转后只会交换 A,B,C,D 的相对顺序，并不会改变 A,B,C,D 的块内心态，记每块的大小为 m，对 n 的奇偶性分别讨论：

• n 为奇数时

  此时 m=n2−14

  • 某个网格在旋转 0∘ 时出现过

    任何的网格都符合这样的要求，这样的网格共有 2n×n 个

  • 某个网格在旋转 180∘ 时出现过

    这要求 A=B,C=D，而中间的那个位置可以随便取色，这样的网格共有 2×2m×2m=22×m+1

  • 某个网格在旋转 90∘ 或 270∘ 时出现过

    这要求 A=B=C=D，而中间那个位置依然可以随便取色，这样的网格共有 2×2m=2m+1 个

  综上，我们得到 4×Sn=2n×n+2m+1+22×m+1+2m+1，当 n>1 时，Sn=2n×n−2+22×m−1+2m，当 n=1 时 Sn=2

• n 为偶数时

  此时 m=n24

  • 某个网格在旋转 0∘ 时出现过

    任何的网格都符合这样的要求，这样的网格共有 2n×n 个

  • 某个网格在旋转 180∘ 时出现过

    这要求 A=B,C=D，这样的网格共有 2m×2m=22×m

  • 某个网格在旋转 90∘ 或 270∘ 时出现过

    这要求 A=B=C=D，而中间那个位置依然可以随便取色，这样的网格共有 2m 个

  综上，我们得到 4×Sn=2n×n+2m+22×m+2m，则 Sn=2n×n−2+22×m−2+2m−1

综上所述，我们得到 Sn 的表达式：

快速幂计算即可

时间复杂度 Θ(log⁡n)

#include<bits/stdc++.h> #define int long longusing 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("%lld\n",(ksm(2,n*n-2)+ksm(2,2*m-1)+ksm(2,m))%MOD); else printf("%lld\n",(ksm(2,n*n-2)+ksm(2,2*m-2)+ksm(2,m-1))%MOD); return 0;}

[BZOJ1361] - [WC2004]孪生项链

Problem Link

根据“Lyndon Word”的经典问题一节中介绍的公式计算即可，注意第一问要写高精度

时间复杂度 Θ(kk+n)，其中 Θ(kk) 的 Θ(k) 是枚举因子数量 Θ(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

从 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={w1,w2,w3,⋯,wk}，满足 S=w1w2w3⋯wk，其中 wi∈LW，且 w1≥w2≥w3≥⋯≥wk

Lyndon 分解定理

Lyndon 分解定理告诉我们，对于任意字符串 S，其 Lyndon 分解存在且唯一

Lyndon 分解的存在性

首先我们把 S 写成 S=S1S2S3⋯S|S|，此时我们就把 S 写成了 |S| 个 LW 的形式

此时对于任意两个相邻的 LW wi,wi+1，若 wi<wi+1 我们就把 wi,wi+1 合并成 wiwi+1 不断重复这个过程直到这样的 wi,wi+1 不存在为止，可以证明这个过程一定会停止，那么我们就得到了一个 Lyndon 分解

Lyndon 分解的唯一性

假设 S 存在两个不同的 Lyndon 分解 w1∼wk 与 w1′∼wk′′

如下图，假设 wi 与 wi′ 是这两个分解第一个不同的地方，且 |wi|>|wi′|，我们设 |wi′wi+1′⋯wi+j′|≥wi，且 |wi′wi+1′⋯wi+j−1′|<wi，显然 j≥1，T 为 wi 与 wi+j′ 的交

根据 w′ 是一个 Lyndon 分解的假设，我们得到 T≤wi+j′≤wi+j−1′≤⋯≤wi′≤wi，又因为 T 是 wi 的一个真后缀，那么 T≤wi 与 wi 是 LW 的要求矛盾，因此这样的 Lyndon 分解必须是唯一的

II. Lyndon 分解的性质

定义 w={w1,w2⋯,wk} 为 S 的 Lyndon 分解，我们有如下的性质：

Lyndon 分解与最小后缀

wk 为 S 的最小后缀，证明如下：

对于长度小于 |wk| 的后缀，根据 wk 是 LW 的事实即可得到所有长度小于 |wk| 的后缀字典序一定大于 wk

而对于任意长度大于 |wk| 的后缀 S′，我们设 S′=wi′wi+1wi+2⋯wk，其中 wi′ 是 wi 的一个后缀，那么根据 Lyndon 分解的定义，wk≤wk−1≤⋯≤wi，且由于 wi′ 是 LW wi 的一个后缀，我们知道 wi′≤wi，因此 wk≤wi′ 又因 |S′|>|wk|，所以 S′>wk

综上，wk 为 S 的最小后缀

Lyndon 分解与最长 LW 后缀

wk 为 S 最大的 LW 后缀，证明如下：

对于任意长度大于 |wk| 的后缀 S′，我们设 S′=wi′wi+1wi+2⋯wk，其中 wi′ 是 wi 的一个后缀，同上面的分析，S′>wk，那么 S′ 必然不可能是 LW

Lyndon 分解与最长 LW 前缀

w1 为 S 最大的 LW 前缀，证明如下：

对于任意长度大于 |w1| 的前缀 S′，我们设 S′=w1w2⋯wi′，其中 wi′ 为 wi 的一个前缀，类似上面的过程，我们得到 wi′≤wi≤wi−1≤⋯≤w1，且 |wi′|<|S′|，因此 wi′<S′，那么 S′ 必然不可能是 LW

III. Duval 算法求 Lyndon 分解

Duval 算法是一种支持在 Θ(|S|) 时间内求出 S 的 Lyndon 分解的算法

我们定义字符串 w′ 为“近似LW”当且仅当存在 w∈LW 使得 w′ 为 w 的一个前缀

那么我们有如下的引理：若 w′ 为一个近似 LW，其中 c 为 w′ 的最后一个字符，如果把 c 修改成一个更大的字符 d ，那么新的 w′ 为一个 LW

不妨设 w′u 为一个 LW，那么考虑 w′ 的一个真后缀 v，记 w=v′v，那么根据 w′u 为 LW，我们知道 vu>w′u，且 |v|<|w′|，考虑 v 和 w′[1⋯|v|] 的大小关系，显然 v≥w′[1⋯|v|]

那么此时考虑增大 w′ 的末尾，那么 v 的末尾会增大且 w′[1⋯|v|] 的末尾不会增大，因此 v>w′[1⋯|v|]，由于 v≠w′[1⋯|v|]，所以 v≫w′[1⋯|v|] 所以 v>w′，故修改后的 w′ 是一个 LW

如下图，在 Duval 算法的过程中，我们将整个字符串 S 分成了三个部分，并且维护了一些变量：

• S1：已经扫描并处理完成的串
• w1∼wg：一些满足 w1≥w2≥⋯≥wg 且 S1=w1w2⋯wg 的一些 LW
• i：S1 的尾指针，满足 S1=S[1⋯i−1]，S2 的头指针
• S2：已经扫描但尚未处理完成的串
• t1∼th：一些满足 t1=t2=⋯=th 的 LW，且 wg>th
• t′：S2 拆分后剩下的一个近似 LW 串，满足 t′ 是 th 的某个前缀
• j：维护 t′ 与 th 的匹配长度
• k：S2 的尾指针，满足 S2=S[i⋯k−1]，t′ 的尾指针，满足 |th|=k−j，S3 的头指针
• S3：未扫描的串

考虑每次将 k 右移一位，并且讨论 Sj 和 Sk 的大小关系

• Sj=Sk，t′ 与 th 继续匹配即可 j←j+1,k←k+1
• Sj<Sk，此时根据引理可以知道新的 t′ 会变成一个 LW 满足 t′>th，那么根据“Lyndon Word 的复合”一节中的结论，tht′ 也是一个 LW，那么由于 tht′>th=th−1 继续重复不断使用该结论即可证明 t1t2⋯tht′ 为 LW，因此设整个 t1t2⋯tht′ 为新的 t1，即 j←i,k←k+1
• Sj>Sk，失配了，此时把 t1∼th 变成 wg+1∼wg+h，后面新生成的 Lyndon 串也不会超过 wg+h=th，并且此时重新匹配 k，记 St 为 t′ 的第一个字符，即 i←t,j←t,k←i+1

复杂度分析

注意到只有 k 会回退，而 i 每次都是增加的且每次回退 k 事实上也不减小 i+k 的值，均摊分析可以证明 Duval 算法的复杂度是 Θ(|S|) 的

根据上面的流程，我们能够写出如下伪代码（记 n=|S|）：

i=1while 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 的所有循环同构串（含自身）中字典序最小的一个

我们有如下的结论：对 S2 进行 Lyndon 分解，设 wi 对应子串 S2[li⋯ri]，那么找到满足 li≤|S|<ri 的 i 则 S2[li⋯li+n−1] 即为 S 的最小表示，证明如下：

对于任意循环同构串 S2[l⋯r]≠S2[li⋯li+n−1]，由于 |S2[l⋯r]|=r−l+1=S，那么 r≤|S|≤ri 总是成立，假设 S2[l⋯r]=wj′wj+1⋯，其中 wj′ 为 wj 的一个后缀，且我们知道 i≤j，那么我们有 wj′>wj>wj+1>⋯>wi，这就证明了 S2[l⋯r]<S[li⋯li+n−1]

V. 习题演练

[洛谷6114] - 【模板】Lyndon 分解

Problem Link

模板题，直接用 Duval 算法求 Lyndon 分解即可

时间复杂度 Θ(|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("%d\n",ans); return 0;}

[洛谷1368] - 【模板】最小表示法

Problem Link

模板题，根据我们上面的分析，先用 Duval 算法求出 {ai}2 的 Lyndon 分解，然后找到满足条件的 wi 即可

时间复杂度 Θ(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;}