Lyndon 分解

Lyndon 串

其严格最小后缀为其本身的串，称为 (Lyndon) 串，也就是 (s) 是其所有循环移位中严格最小的。

(s,t) 都为 (Lyndon) 串是，且 (s<t)，则 (st) 也为 (Lyndon) 串。证明 (t>st) 后即可证明该性质。

Lyndon 分解

(Lyndon) 分解为将 (s) 分解得 (s=s_1s_2s_3 dots s_k)，且 (s_i geqslant s_{i+1})，(Lyndon) 分解是存在且唯一的。

存在性由 (Lyndon) 串的性质不难得到，唯一性可以用反证法来证明。

Duval 算法

(Duval) 算法可以 (O(n)) 求出一个串的 (Lyndon) 分解。

对于字符串 (s) 和字符 (c)，若 (sc) 是某个 (Lyndon) 串的前缀，则对于字符 (d>c) 有 (sd) 是 (Lyndon) 串。

维护三个指针 (p,i,j)。([1,p-1]) 是已经进行完 (Lyndon) 分解的部分，([p,j-1]) 为 (s_1s_2s_3 dots s_kt)，其中 (t) 可以为空串，且 (s_1) 是 (Lyndon) 串和 (s_1=s_2= dots =s_k)，(t) 是 (s_1) 的前缀，满足 (s[p,j-1]) 比上一个分解出的串小。

当前加入字符 (s_j)，令 (i=j-|s_1|)，即为 (t) 在循环串对应的位置。进行分类讨论：

当 (s_i=s_j) 时，(t) 能继续匹配，让 (i,j) 都向后移动一个位置。

当 (s_i<s_j) 时，得 (s[p,j]) 为 (Lyndon) 串，将 (i) 移动到 (p)，(j) 向后移动一个位置。

当 (s_i>s_j) 时，得 (s_1s_2s_3 dots s_k) 为分解后的串，然后继续考虑 (t)，(j) 向后移动一个位置。

因为 (p) 只向后移动，(j) 向前移动的距离不超过 (p) 向后移动的距离，所以复杂度为 (O(n))。

while(p<=n)
{
    int i=p,j=p+1;
    while(j<=n&&s[i]<=s[j]) i=s[i]==s[j++]?i+1:p;
    while(p<=i) p+=j-i,ans^=p-1;
}

这段代码求的是 (Lyndon) 分解所有右端点的异或和。

应用

求解最小循环表示，(O(n)) 对所有 (s[1,i]) 求最小最大后缀。