定义

• 一个字符串 s 是 Lyndon Word，当且仅当 s 是其所有后缀中字典序最小的；
• 将字符串 s 分为若干部分 s_1s_2\cdots s_m，使得每个 s_i 都是 Lyndon 串，且 \forall 1\leq i<m,s_i\geq s_{i+1}，则称这个划分为字符串 s 的 Lyndon 分解。

性质

• 任意字符串 s 存在 Lyndon 分解。

  • 引理：若 u,v(u<v) 为 Lyndon 串，则 uv 也是 Lyndon 串。

  证明：

  uv 的后缀可以被分为两类：一类是 u 的后缀加上 v，这部分的相对大小是不会改变的；另一类是 v 的后缀，因为 v 是 Lyndon 串，所以 v 是所有这一类后缀中最小的。也就是说我们只需要证明 uv<v，这由 u<v 易知成立。

  证明：

  对于 s 任意一个划分 s_1s_2\cdots s_m，且每个 s_i 都是 Lyndon 串，如果它不是 Lyndon 分解，则一定 \exists 1\leq k<m,s_k<s_{k+1}。由引理知 s_k 和 s_{k+1} 可以合并成一个 Lyndon 串。显然当个字符是 Lyndon 串，因此我们可以构造全是当个字符的划分，并不断合并得到一个 Lyndon 分解。于是原命题得证。

• 任意字符串 s 的 Lyndon 分解唯一。

  证明：

  假设存在两种不同的划分 s_1s_2\cdots s_m 和 s'_1s'_2\cdots s'_{m'}，取最小的 i 使得 s_i\neq s'_i。不妨设 |s_i|>|s'_i|，令 s_i=s'_{i}s'_{i+1}\cdots s'_{k}s'_{k+1}[1\dots l]。由定义得 s_i<s'_{k+1}[1\dots l]\leq s'_{k+1}\leq s'_i<s_i，导出矛盾，原命题得证。

Duval 算法

Duval 算法是一种能线性求出任意字符串 s 的 Lyndon 分解的算法。

这种算法运行过程中把 s 分成三部分：s_1s_2\cdots s_g 表示已经固定下来的分解，即一个前缀的 Lyndon 分解；t_1t_2\cdots t_hv 表示没有固定的分解，满足周期性，即 t_1=t_2=\cdots=t_h，且 v 是 t_1 的前缀；第三部分是还没有处理到的部分。

设现在加入字符 s[k]，考虑其与 s[k-|t_1|] 的关系，分三种情况讨论：

• s[k]=s[k-|t_1|]。此时周期 t_1 将继续保持；
• s[k]>s[k-|t_1|]。此时合并 t_1\gets t_1t_2\cdots t_hvs[k]，由引理知其是 Lyndon 串；
• s[k]<s[k-|t_1|]。此时 t_1t_2\cdots t_h 的分解被固定，而 vs[k]<t_1，令 t_1\gets vs[k] 并继续。

实现很简单，只需维护三个单调右移的指针即可。下面是 洛谷模板题 的代码：

#include <cstdio>
#include <cstring>
const int MAXN=5500000;
char s[MAXN];
int main()
{
    scanf("%s", s+1);
    int n=strlen(s+1), ans=0;
    for (int i=1; i<=n; )
    {
        int j=i, k;
        for (k=i+1; k<=n&&s[k]>=s[j]; k++)
            if (s[k]>s[j]) j=i; else j++;
        while (i<=j) ans^=i+k-j-1, i+=k-j;
    }
    printf("%d\n", ans);
    return 0;
}