Lyndon Word

定义:对于字符串$s$,若$s$的最小后缀为其本身,那么称$s$为Lyndon串

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

性质

任意字符串$s$都可以分解为$s = s_1 s_2 \dots s_k$,其中$\forall s_i$为Lyndon串且$s_i \geqslant s_{i +1}$。且这种分解方法是唯一的

  • 存在性

引理1:若$u, v$为Lyndon串,且$u < v$,那么$uv$为Lyndon串

证明:
要证明$uv$为Lyndon串只需证明$uv$本身为其最小后缀,
我们可以把所有的后缀分为两类,一类是由$u$的后缀加上$v$串的来,这部分的相对大小不会改变。
另一类是$v$串的后缀,因为$v$本身也是Lyndon串,我们只需证明$v > uv$,因为$v > u$,显然成立

  • 唯一性

证明:
设$pre(s, i)$表示串$s$中$s[1 \dots i]$所代表的前缀
若有两种方案,取第一次不同的位置,设$|s_i| > |s’_i|$
令$s_i = s’_i s’_{i + 1} \dots s’_{k} pre(s_{k + 1}, l)$
反证法。根据定义,$s_i < pre(s’_{k + 1}, l) \leqslant s’_{k + 1} \leqslant s’_i < s_i$
矛盾

Duval算法

(下面内容抄袭并补充自参考资料2)

该算法可以在$O(n)$的时间内求出串$s$的Lyndon分解

测试地址

引理2:若字符串$v$和字符$c$满足$vc$是某个Lyndon串的前缀,则对于字符$d>c$有$vd$是Lyndon串

证明:和上面同样的思路,对于$d$之前的后缀相对大小不会改变,之后的后缀只会变大

该算法中我们仅需维护三个变量$i, j, k$

$s[1..i - 1] = s_1 s_2 \dots s_g$是固定下来的分解,也就是$\forall l \in [1, g] s_l$是Lyndon串且$s_l > s_{l + 1}$

$s[i .. k - 1] = t_1 t_2 \dots t_h v(h > 1)$ 是没有固定的分解,满足$t_1$是Lyndon串,且$t_1 = t_2 = \dots = t_h$,$v$是$t_h$的(可为空的)真前缀,且有$s_g > s[i .. k - 1]$

当前读入的字符是$s[k]$,令$j = k - |t_1|$

分三种情况讨论

  • 当$s[k] = s[j]$时,周期$k - j$继续保持

  • 当$s[k] > s[j]$时,合并得到$t_1 <- t_1 t_2 \dots t_h v s[k]$是Lyndon串

  • 当$s[k] < s[j]$时,$t_1, t_2, \dots, t_h$的分解被固定下来,算法从$v$的开头处重新开始

#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

金策—字符串选讲


一只菜鸡