Lyndon Word学习笔记

程序员文章站 2022-04-05 10:04:58

Lyndon Word 定义：对于字符串$s$，若$s$的最小后缀为其本身，那么称$s$为Lyndon串等价性：$s$为Lyndon串等价于$s$本身是其循环移位中最小的一个性质任意字符串$s$都可以分解为$s = s_1 s_2 \dots s_k$，其中$\forall s_i$为Lynd ......

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;
}