Lyndon 分解

(Updated: )
(1 min to read)

概念

Lyndon串：s是s所有后缀中字典序最小的（s是其所有循坏位移中最小的一个）Lyndon分解：Lyndon 分解是将字符串 s 分解成 $s=s_1s_2 \dots s_n$​,使得每个$s_i$​都是Lyndon串，且$s_i\geq s_{i+1}$

性质

Lyndon分解唯一，且每个字符串都存在Lyndon分解。

Duval 算法

$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i=1; i<=n; )
{
  int j = i, k = i+1;
  while(k<=n&&s[j]<=s[k])
  {
    if(s[j]<s[k]) j = i;
    else j++;
    k++;
  }
  while(i<=j)
  {
    ans ^= i+k-j-1;  // [i:i+k-j-1]是某个分解的s_i
    i += k-j;
  }
}

最小表示法只要对s+s进行Lyndon分解并找到最后一个分解的串的起点取长度n即可