性质

$S$ 是Lyndon串当且仅当 $S$ 本身是所有后缀中的最小串。$S$ 是Lyndon串可以推出 $S$ 是所有循环表示中字典序最小的。

各种性质与推论：

1. $A,B$ 都是Lyndon串且 $A<B$ ，则 $A+B$ 也是Lyndon串，因为 $B>A+B$ 。
2. 如果 $S=A+B$ 是Lyndon串，则 $B>S>A$ 。
3. $S$ 可以唯一划分成 $A_1A_2\cdots A_m$ ，其中 $A_i$ 均为Lyndon串，且 $A_i\ge A_{i+1}$ ，划分方法即Lyndon分解。

4. 若Lyndon串 $S=A+c+B$ ，则 $A+d$ 是Lyndon串（其中 $c,d$ 为字符，且 $d>c$ ）。

   证明：$suf(A)+c+B\ge A+c+B,suf(A)+c\ge A,suf(A)+d> A,d>c\ge A[1]\Rightarrow suf(A)+d\ge A+d$ 。

5. Lyndon串没有Border，所以Lyndon串也没有周期。

Lyndon分解的暴力划分：刚开始 $A_i=S_i$ ，如果 $A_i<A_{i+1}$ 则合并 $A_iA_{i+1}$ 。

分解

Duval算法可以进行Lyndon分解。

维护三个位置 $i,j,k$ ，$S[1,i-1]$ 已经分解完毕。现在 $S[i,k-1]=A^{t}+B$ ，其中 $A$ 是Lyndon串，$A^t$ 是多个 $A$ 接一起。

$B$ 是 $A$ 的可空前缀，$j=k-|A|$ 表示 $S_k$ 在 $A$ 中的对应位置，接下来考虑加上 $k$ 这个位置：

1. $S_k=S_j$ ，则 $A$ 仍是周期，$j,k$ 均往后移动。
2. $S_k>S_j$ ，根据性质3，$B+k$ 是Lyndon串，并且 $A<B+k$ ，前面全部合并，新的 $A$ 更新为 $S[i,k]$ 。
3. $S_k<S_j$ ，则 $A>B+k$ ，所有的 $A$ 都已经确认分解完毕，将 $i$ 移动到 $B$ 的开头。

for (int i=1;i<=n;){
    int j=i,k=j+1;
    for (;k<=n && s[k]>=s[j];k++) s[k]==s[j]?j++:j=i;
    for (;i<=j;i+=k-j) L[++m]=i,R[m]=i+(k-j)-1;
}

由于 $|B|<|A|$ ，因此 $k$ 的移动距离最多为 $2\Delta i$ ，$i$ 的移动距离为 $\Delta i$ ，由于 $i$ 只增不减因此复杂度 $O(n)$ 且常数较小。

注意到Duval算法其实是不断地枚举周期，下面会用到这个性质。

例题

洛谷6114 【模板】Lyndon 分解

模板题，直接用上面代码即可。

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

把串再接一遍，最后一个 $L_i\le n$ 的Lyndon串就是最小的循环串。

因为 $A_i\ge A_{i+1}$ ，所以显然最后一个在前半部分出现的Lyndon串就是最小的。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=600000;

int n,pos,s[maxn+5];

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&s[i]),s[i+n]=s[i];
    n<<=1;
    for (int i=1;i<=n;){
        int j=i,k=j+1;
        for (;k<=n && s[k]>=s[j];k++) s[k]==s[j]?j++:j=i;
        for (;i<=j;i+=k-j) if (i<=(n>>1)) pos=i;
    }
    for (int i=pos;i<=pos+(n>>1)-1;i++)
        printf("%d",s[i]),i<pos+(n>>1)-1?putchar(' '):puts(" ");
    return 0;
}

这样求出的是最大位置，如果要最小位置，对于每次的循环串只取第一个 $i$ 即可。

HDU6761 Minimum Index

求每个前缀的最小后缀。

对于一个前缀，Lyndon分解之后，显然最小后缀就是最后一个Lyndon串。因为如果最小后缀能往前推，则显然不满足 $A_i\ge A_{i+1}$ 。

观察算法过程，其实 $k$ 移动的过程包含着前缀的Lyndon分解过程：

1. 当 $S_k=S_j$ 时，仍处于周期串 $A$ 中，由于周期串的答案已经求出，因此 $k$ 可以从上一次对应的位置继承答案，即 $ans_k=ans_j+k-j$ 。
2. 当 $S_k>S_j$ 时，新的Lyndon串为 $S[i,k]$ ，因此 $ans_k=i$ 。
3. 当 $k>n$ 或 $S_k<S_j$ 时，多出来的一段 $ans$ 作废，留到之后处理（之后覆盖 $ans$ ）。

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=1e9+7;

int te,n,ans[maxn+5];char s[maxn+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%s",s+1);n=strlen(s+1);
        for (int i=1;i<=n;){
            int j=i,k=j+1;
            ans[i]=i;
            for (;k<=n && s[k]>=s[j];k++)
                if (s[k]==s[j]) ans[k]=ans[j]+k-j,j++;
                else ans[k]=i,j=i;
            for (;i<=j;i+=k-j);
        }
        int ha=0;
        for (int i=1,pw=1;i<=n;i++,pw=MUL(pw,1112)) ha=ADD(ha,MUL(pw,ans[i]));
        printf("%d\n",ha);
    }
    return 0;
}

2021ICPC沈阳M String Problem

和上面题相反，要求每个前缀的最大后缀。

最大后缀不是简单的将字符集反转就可以得出的。因为在 $A$ 是 $B$ 前缀时，$A<B$ ，但字符集翻转之后还是 $A'<B'$ ，因此是错的。

但是不难发现，字符集翻转后对于前缀进行Lyndon分解，如果最大后缀不是最后一个Lyndon串，则一定是将这个Lyndon串作为前缀的串（因为按照前面的说明，只有 $A$ 作为 $B$ 前缀时，字符集翻转后大小关系出现错误）。

所以我们还是可以考虑用周期的性质和（字符集翻转后的）Lyndon分解来求出最大后缀：

1. 当 $S_k=S_j$ 时，仍处于周期串 $A$ 中，考虑继承答案 $ans_k=ans_j+k-j$ ，但由于是周期串，所以 $S[ans_j+k-j,k]$ 一定是 $S[ans_j,k]$ 的前缀，所以 $ans_k=ans_j=\cdots =ans_i=i$ 。
2. 当 $S_k<S_j$ 时，新的Lyndon串为 $S[i,k]$ ，则 $ans_k=i$ 。
3. 当 $k>n$ 或 $S_k>S_j$ 时，多出来的一段不作废。

不作废是因为多出来的一段是 $A$ 的前缀，处理过程一致，则后来划分的Lyndon串肯定是之前答案的前缀，因此不会有之前的答案优秀。

注意，上面 $ans$ 均表示在 $i$ 开头考虑时的答案，而不是最终答案。所以不作废的意思就是在最终答案没有的情况下才更新 $i$ 开头的答案。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000;

int n,ans[maxn+5];char s[maxn+5];

int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for (int i=1;i<=n;){
        int j=i,k=j+1;
        if (!ans[i]) ans[i]=i;
        for (;k<=n && s[k]<=s[j];k++){
            if (!ans[k]) ans[k]=i;
            s[k]==s[j]?j++:j=i;
        }
        for (;i<=j;i+=k-j);
    }
    for (int i=1;i<=n;i++) printf("%d %d\n",ans[i],i);
    return 0;
}