Lyndon Word:

定义：对于字符串??，若??的最小后缀为其本身，那么称??为Lyndon串

等价性：??为Lyndon串等价于??本身是其循环移位中最小的一个

重要性质: 任意字符串??都可以分解为??=??1??2…????，其中?????为Lyndon串且?????????+1。且这种分解方法是唯一的

---------------------------------------------------------------------

Lyndon的分解:Duval算法

该算法可以在??(??)的时间内求出串??的Lyndon分解

lyndon 分解

#include<bits/stdc++.h>
using namespace std;
const int MAXN = (1 << 21) + 1;
char s[MAXN];
int main() {
    scanf("%s", s + 1);
    int N = strlen(s + 1), j, k;
    for(int i = 1; i <= N;) {
        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) {
            printf("%d ", i + k - j - 1);
            i += k - j;
        }
    }
    return 0;
}

.

.

.

.

参考自为风月马前卒

lyndon word 学习笔记&

原文：https://www.cnblogs.com/naruto-mzx/p/12157851.html