Lyndon & Runs 学习笔记

概念定义与符号约定

字符串一般记大写字母 $S,A,B$ （下面的字符串基本都不能是空的，但还是请根据语境自行判断），空字符串用 $\emptyset$ ，确定的字符用字体 $\mathrm{abcde}$ 表示（基本不会在定理和证明中出现，只会在例子中出现），不定字符用小写字母 $xyz$ 表示。

对于字符串 $S$ ：

• 长度：$|S|$ ，有时候用 $n$ 代替。
• 字符：$S[i]$ 表示字符串的第 $i$ 个字符，下标从 $1$ 开始。
• 字符集：$\sum_{S}$
• 子串：$s[l,r]$ 表示 $s[l]s[l+1]…s[r]$ 。

• 前缀&后缀：$S\langle i]=S[1,i]$，$S[i\rangle=S[i,n]$ 。

  称一个前缀/后缀为严格的，单且仅当它≠原串 $S$ 。

  记 $\mathrm{pre}(S)$ 为前缀集合，$\mathrm{suf}(S)$ 为后缀集合， $\mathrm{pre}’(S)$ 为严格前缀集合，$\mathrm{suf}’(S)$ 为严格后缀集合。

• 出现位置：对于串 $t$ ，记：

  $\mathrm{Beg}_{S}(t)$ 为 $t$ 在 $S$ 中所有出现位置的左端点集合。

  $\mathrm{End}_{S}(t)$ 为 $t$ 在 $S$ 中所有出现位置的右端点集合。

  对于区间集合 $L$ ，类似地记：

  $\mathrm{Beg}(L)$ 为 $L$ 地左端点集合。

  $\mathrm{End}(L)$ 为 $L$ 地右端点集合。

• 字符串的拼接,幂 ： 记 $st$ 。 $S\cdot t$ 为字符串 $S,t$ 顺次连接而得的串。

  定义 ： $S^k=\overbrace{ss\ldots S}^{\text{共 k 个}}$ ，即 $S$ 重复 $k$ 次后形成的串。

• 循环节 $\mathbf{period}$：若对于所有 $1\leq i\leq n-c$ ，均有$s_i=s_{i+c}$ ,则称 $c$ 是 $S$ 的一个循环节。

  若 $c|n$ 则称$c$为整周期。

  记 $\mathrm{period}(S)$ 为 $S$ 的循环节集合。

• Border : 若有 $S\langle i]=S[n-i+1\rangle\left(1\leq i<n\right)$ （等于后缀的严格前缀） ，则称之为 $\mathrm{Border}$ ，简称为 $\mathrm{Bd}$

  记 $\mathrm{Bd}(S)$ 为 $S$ 的 Bd 集合。（ 注意 $S\not\in\operatorname{Bd}(S)$ ）

  $\mathrm{Bd}$ 和 $\mathrm{period}$ 是一一对应的。其中，一个长度为 $k$ 的 $\mathrm{Bd}$ 对应一个长度为 $n-k$ 的循环节。

• 串 $S$ 的循环位移：$S$ 和 $\forall 1\le i<|S|,S[i+1\rangle S\langle i]$ 所构成的字符串集合称为 $S$ 的循环位移。

• Lyndon Word: 若字符串 $S$ 的最小后缀是其本身，即 $S<\mathrm{suf}^{\prime}(S)$ ,则称之为 $\mathrm{Lyndon Word},简称为 $\mathrm{Ly}$。

  例：$abc,ababc$ 是 $\mathrm{Ly}$ ，而 $ba,acabc$ 不是。

• Lyndon 分解 ：$L_1L_2,…,L_k$ 称为 $S$ 的 $\mathrm{Lyndon}$ 分解当且仅当：$L_i\ge L_{i+1}$ ，且 $L_{i}$ 是 $\mathrm{Ly}$ 。

• Runs: 三元组 $\mathbf{r}=(l,r,p)$ 是串 $S$ 的一个 $\mathrm{run}$ ,当且仅当：

  • $S[l,r]$ 的最小循环节为 $p$ ，满足 $2p\leq\left|S[l, r]\right|=r-l+1$
  • 该循环不能延伸，即 $S[l-1]\neq S[l+p-1],S[r+1]\neq S[r-p+1]$

  实数 $e_{\mathrm{r}}=\frac{r-l+1}p$ 被称为该 $\mathrm{run}$ 的指数记 $\mathrm{Runs}(S)$ 为 $S$ 的所有 $\mathrm{run}$ 构成的集合。$\rho_{\mathrm{run}}(n)$ 表示长度为 $n$ 的字符串中至多含有的 $\mathrm{run}$ 个数。$\sigma_{\mathrm{run}}(n)$ 表示长度为 $n$ 的字符串的 $\mathrm{run}$ 的指数和的最大值。

• 设 $sa[i]$ 表示在后缀排序中 ，排名第 $i$ 的后缀是 $S[sa[i]\rangle$ ，$rk[i]$ 表示 $S[i\rangle$ 的排名。

上面的符号和定义部分使用了 command_block 博客的符号，这些符号有部分是他个人规定的，并不完全正规。

字符串的基本性质

字符串比较都认为虚空最小，在此基础上有两种视角，第一种：将比较的字符通过在末尾填虚空的方式，填到等长，比较。第二种是直接关于长度进行讨论。我个人喜欢第二种，至少目前是，个人感觉第一种只能用在比较简单的性质上，直观易懂，但第二种比较灵活。

性质 1 （字符串不等式的传递性）：若 $A<B,B<C$ ，则 $A<C$ 。（换成非严格不等号一样）

性质 2 ： $A<B$ 当且仅当 $CA<CB$ 。（换成非严格不等号一样）

性质 3 ：若 $|A|=|B|$ ，且 $AC<BD$ ，则 $A\le B$ 。

性质 4 ：若 $|A|\ge |B|$ ，$A<B$ ，则 $AC<B$ 。

性质 5 ：若 $A\ge B$ ，则对于所有的 $i$ 有 ：$A\langle i] \ge B\langle i]$ 。（假设 $|A|<i$ ，则 $A\langle i]=A$ ，$B$ 同理）

证明

两种情况讨论一下就行了：$B$ 是 $A$ 的前缀和 $B$ 不是 $A$ 的前缀（因为字符不同产生的 $>$）。

Lyndon Word

重要的性质

性质 1 ： $\mathrm{Ly}$ 串 $S$ 没有 $\mathrm{Bd}$ 。

性质 2 ：一个串 $S$ 是 $\textrm{Ly}$ 当且仅当 $S$ 是 $S$ 的所有循环位移中严格唯一最小的一个。

证明

必要性：设 $S=AB$ ，故 $BA>B>AB$ ，证毕，

充分性：$AB|B|$） ，则有 $BCB<BBC$ ，又有：$CBB<BCB$ ，但是根据假设有：$AB=BCB<CBB$ ，矛盾。

若 $|A|<|B|$ ，若 $A\notin\mathrm{pre}(B)$ ，同理 $AB<B$ 。

否则设 $B=A^KC(k\ge 1)$ ，满足 $A\notin \mathrm{pre}(C)$ ，故有 $A^{k+1}CA^{k+1}C=S$ ，若 $|C|\le |A|$ ，则有 $C>A$ ，故有 $A^{k}C>A^{k+1}$ ，故有 $B>S$ ，否则 $|C|>|A|$ ，则有 $C\langle i]>A$ ，同理 $B>S$ ，证毕。

推论 ：$S$ 的循环位移有严格唯一最小值当且仅当 $S$ 没有整周期。

证明

显然，$S$ 的循环位移同时有或没有整周期。

若有严格唯一最小值，设 $S’$ 为最小值，则 $S’$ 为 $\mathrm{Ly
}$ ，所以 $S’$ 无 $\mathrm{Bd}$ ，所以无整周期。

否则设 $S’$ 是其中一个最小值， $S’=AB$ ，其中 $BA$ 为另外一个最小值 ，则 $A,B$ 都是 $S’$ 的周期，故 $S’$ 有整周期 $(|A|,|B|)$ （最大公约数），证毕。

其实这个结论不用 Lyndong Word 也很好证明，证明 $S$ 在有整周期的情况下不可能有唯一最小值就行了。

性质 3 ： $\mathrm{Lyndon}$ 分解若存在，则唯一。

证明

设 $L_{1}L_{2}…L_{k}$ 和 $L’_{1}…L’_{m}$ 都是 $S$ 的 $\mathrm{Ly}$ 分解，不妨设 $|L_{1}|<|L’_{1}|$ （否则考虑 $S’=L_{2}…L_{k}=L’_{2}…L’_{m}$）。

设 $t$ 为最小的满足：$L’_{1}\in \mathrm{pre}(L_{1}L_{2}…L_{t})$ ，设 $S=L_{t}\langle|L’_{1}|-\sum\limits_{i=1}^{t-1}|L_{i}|]$ ，$S\le L_{t}\le L_{1}<L’_{1}$ ，但 $S>L’_{1}$ ，矛盾，证毕。

性质 4 ：若 $A<B$ ，且 $A,B$ 都是 $\mathrm{Ly}$ ，那么 $AB$ 是 $\mathrm{Ly}$ 。

证明

$\forall T\in \mathrm{suf}’(AB)$ ，若 $|T|>|B|$ ，则有：$T\langle |T|-|B|]>A$ ，则有：$T>AB$ 。

若 $|T|\le |B|$ ，则有 $A<B<T$ ，证毕。

性质 5 ：$S$ 的 $\mathrm{Lyndon}$ 分解一定存在。

证明

$\forall 1\le i\le |S|,L_{i}=S_{i}$ 。

考虑调整，若 $L_{i}>L_{i+1}$ ，则合并，直到没有为止，则为一组解，证毕。

推论：若 $L_{1}L_{2}…L_{k}=S$ ，$L_{i}$ 为 $\mathrm{Ly}$ ，设 $L’_{1}…L’_{t}$ 为 $S$ 的 $\mathrm{Lyndon}$ 分解 ，则存在 $0=a_{0}<a_{1}<a_{2}<…<a_{t}=k$ 满足：$L_{a_{i-1}+1}…L_{a_{i}}=L’_{i}$ 。

证明方法和性质 5 一样，在此不再赘述。

所以一个串 $S$ 的 $\mathrm{Lyndon}$ 分解存在且唯一。

性质 6 ：若 $S=L^kA$ 满足：$L$ 为 $\mathrm{Ly}$ ，$L^{k}\ge A$ ，则设 $L_{1}…L_{t}$ 为 $A$ 的 $\mathrm{Lyndon}$ 分解，则 $L^{k}L_{1}…L_{t}$ 为 $A$ 的 $\mathrm{Lyndon}$ 分解。

证明

反证法，如果 $L_{1} > L$ ，那么如果 $|L_{1}|\le |L|$ ，那么有 $A>L^{k}$ 矛盾。

否则若 $|L_{1}|>L$ ，同理可得到 $L\in \mathrm{pre}(L_{1})$ （否则和上面的情况没区别），设 $L_{1}=L^{v}B$ ，$L\notin \mathrm{pre}(B)$ ，其中，根据 $L^{k}\ge A$ 以及 $L_{1}>L$ ，$L$ 是个 $\mathrm{Ly}$ ，可以得到 $v<k,B≠\emptyset$ 。

那么 $B\notin \mathrm{pre}(L)$ ，否则，不构成 $\mathrm{Ly}$ ，所以可以根据 $L_{k}\ge S$ 得到 $B<L$ （由于字符不同产生的小于），所以 $B<L_{1}$ ，矛盾，证毕。

性质 7 ：设 $i$ 是第一个 $rk_{i}<rk_{1}$ 的数字，如果不存在， $i=|S|+1$ ，那么有 $L_{1}=S\langle i-1]$ 。

证明

先证明 $S\langle i-1]$ 是 $\mathrm{Ly}$ ：

设 $1rk_{1}$ ，则有 $S_{j,i-1}\ge S_{1,i-j}$ 。

若 $S_{j,i-1}=S_{1,i-j}$ ，则有 $rk_{i}>rk_{i-j+1}>rk_{1}$ ，矛盾，故 $S_{j,i-1}>S_{1,i-j}$ ，故 $S_{j,i-1}>S\langle i-1]$ ，证毕。

设 $A=S\langle i-1]$ ，$S=AB$ ，已知 $B<AB$ ，若 $A<B$ ，则有 $A\in\mathrm{pre}’(B)$ ，若 $S=A^{k}$ ，则显然 $L_{1}=A$ ，否则若 $S=A^{k}C$ ，即 $B=A^{k-1}C$ ，$A\notin \mathrm{pre}(C)$ ，则有 $C<A<A^{k}$ ，根据性质 $6$ 可以知道 $L_{1}=A$ 。

证毕。

这个性质可以用于在 $O(n\log{n})$ 的时间找到 $\mathrm{Lyndon}$ 分解，而且在求每个后缀的 $\mathrm{Lyndon}$ 分解的相关问题上有奇效。

可以用一个单调栈，从后往前跑出所有后缀的 $\mathrm{Lyndon}$ 分解。

性质 8 ：如果 $S$ 和字符 $x$ 满足 $Sx\in \mathrm{pre}(L)$ ，$L$ 是个 $\mathrm{Ly}$ ，那么 $\forall y>x,Sx$ 是 $\mathrm{Ly}$ 。

证明

显然 ，$y>S_{1}$ ，如果 $\exists 1<i\le |S|:S[i\rangle y \le Sy$ ，那么 $S[i\rangle x<S[i\rangle y\le Sy$ ，而且一定是因为字母比较产生的 $<$ ，所以 $S[i\rangle x<L$ ，矛盾。

推论：把 $L$ 改成 $L^{k}$ 仍然正确，因为在 $L^k$ 后面加上一个无限大字符后 ，得到的 $L’$ 仍然是 $\mathrm{Ly}$ 。

Duval 算法

定义 $T$ 为近似 $\mathrm{Ly}$ 当且仅当 $S=L^{k}\overline{L}$ ，其中 $\overline{L}=\mathrm{pre}’(L)$ ，$\overline{L}$ 可以为空。

整个算法采用增量的方式去找到 $\mathrm{Lyndon}$ 分解 。

假设 $S=L_{1}L_{2}…L_{k}T$ ，其中 $T$ 为近似 $\mathrm{Ly}$ ，$T=L^{t}\overline{L}$ 。（其中 $L_{i}$ 为已经确定的部分，可以不用管了）

假设现在加入字符 $c$ 。

1. 如果 $c=L_{|\overline{L}+1|}$ ，那么继续，扩展 $T$ 。
2. 如果 $c<L_{|\overline{L}+1|}$ ，那么根据上面的性质 $6$ ，可以知道 $L^{t}$ 可以扔出去了，然后剩下的部分继续处理。
3. 如果 $c>L_{|\overline{L}+1|}$ ，那么根据根据性质 $8$ 的推论可以知道 $Tc$ 此时是个 $\mathrm{Ly}$ ，更新 $T=L=Tc$ 。

直到最后，如果 $\overline{L}=\emptyset$ ，则结束，否则 $L^t$ 扔出去，继续处理 $\overline{L}$ 。

下面代码中，$i=|L_{1}…L_{k}|+1,k=|L_{1}…L_{k}T|-|L|+1,j=|L_{1}…L_{k}T|+1$

for(int i = 1; i <= n;){
    int j = i + 1, k = i;
    for(; j <= n && st[k] <= st[j]; j++){
        if(st[k] < st[j]) k = i;
        else k++;
    }
    for(; i <= k; i += j - k) ;
    //[i,i+j-k)即为对应的Lyndon分解 
}

时间复杂度：注意到每层循环下来，$i$ 会加上 $\frac{j-i+1}{2}$ ，而内层每层循环 $j$ 会 $+1$ ，所以内层最多跑 $2n$ 次，外层每次 $i$ 至少 $+1$ ，所以至多跑 $n$ 次，所以总时间复杂度：$O(n)$ 。

相比起后缀数组求法，Duval 算法在求每个前缀的 $\mathrm{Lyndon}$ 分解的问题上有奇效。

UPD：这里补充一下所谓的已经完成的 $\mathrm{Ly}$ 的意思是什么，意思是 $\forall j\ge i$ ，$S\langle j]$ 的 $\mathrm{Lyndon}$ 分解都是 $S\langle i-1]$ 的分解拼接上 $S[i-1,j]$ 的分解，熟悉这个理解有助于后面理解求前缀最小/大后缀的做法。

一些补充的性质

可以自己证证玩玩的性质。

性质 9 ：对于 $\mathrm{Ly}$ $A=BC$ ，由 $B<C$ 。

证明

$B<BC<C$

性质 10 ：$\mathrm{Ly}$ 串 $S$ 的任意子串 $S_{l,r}\ge S\langle r-l+1]$ ，且若 $r=|S|$ ，则改为严格不等号。

这个性质某种意义上很重要，它反映了 $\mathrm{Ly}$ 串的一个性质：在求字符串的最小解问题时，$\mathrm{Ly}$ 串往往作为一个整体存在。在后面的例题中我们能更加直观的看到这一点。

性质 11 ：对于 $\mathrm{Ly}$ $B$ 和另一个串 $A$ ，有 $A<B\Leftrightarrow AB<B$ 。

证明

$\leftarrow$ ：$A<AB<B$ 。

$\rightarrow$ ：若 $A\notin \mathrm{pre}(B)$ ，则显然成立（因为 $<$ 由字符不同产生，而不是长度不同）。

否则设 $B=AC$ ，即证明：$AAC<AC$ ，即证明 $AC<C$ ，由 $\mathrm{Ly}$ 定义可得，证毕。

性质 12 ：$A$ 是 $\mathrm{Ly}$ ，且 $|A|\ge 2$ ， 则一定存在 $S=AB,A<B$ ，且 $A,B$ 均为 $\mathrm{Ly}$ 。（这可以看作上面性质 $4$ 的一个反方向）

证明 1

先证明一个引理：如果 $S=ABC$ ，其中 $C$ 是 $\mathrm{Ly}$ ，那么 $AC$ 是 $\mathrm{Ly}$ 。

对于 $AC$ ，$\forall T\in \mathrm{suf}’(AC)$ ，如果 $A\notin \mathrm{pre}(T)$ ，那么由于 $T>ABC$ 可以得到 $T>A$ （因字符不同而产生的 $>$），所以 $T>AC$ ，否则有 $T=AD$ ，那么有 $D>C$ ，$AD>AC$ ，证毕。

那么设 $B$ 为 $\mathrm{suf}’(S)$ 中最长的是 $\mathrm{Ly}$ 的串，则 $S=AB$ ，$A$ 不能有 $\mathrm{Bd}$ ，否则 $B$ 可以伸长，矛盾。

所以 $\forall T\in \mathrm{suf}’(A)$ ，如果 $TA$ ，所以 $A$ 是 $\mathrm{Ly}$ ，证毕。

证明 2

来自 cmd 的证明。

考虑 $S[i\rangle$ 是最小的严格后缀。

那么显然 ，$S[i\rangle$ 是 $\mathrm{Ly}$ 。

现证明 $S\langle i-1]$ 是 $\mathrm{Ly}$ ，显然只需要证明 $S\langle i]$ 没有 $\mathrm{Bd}$ 即可。

假设有长度为 $k$ 的 $\mathrm{Bd}$ ，那么有：$S[1,k]=S[i-k,i-1]$ ，根据前面的定义，有 $S_{k+1}>S_{i}$ 。（这里也可以用我证明中的引理，证明 $S[i-k\rangle$ 是 $\mathrm{Ly}$ ，所以 $rk[i-k]<rk[i]$ ，矛盾）

所以 $S>S_{i-k}$ ，矛盾，证毕。

性质 13 ：$S=L_{1}…L_{k}$ ，则 $1\le iL_{j}…L_{k}$ 。

证明

从后缀数组的角度看显然，因为排名递降。

但是从 $\mathrm{Lyndon}$ 角度看呢？

不妨假设 $L_{i}≠L_{j}$ ，否则去掉 $L_{i}$ 直接归纳，即认为 $L_{i}>L_{j}$。

如果 $|L_{i}|\le |L_{j}|$ ，那么根据上面假设，显然成立。

否则假设 $t$ 为最小的数字满足： $|L_{j}L_{j+1}…L_{t}|\ge L_{i}$ ，那么有：

$\forall j\le v \le t-1,L_{v}\le L_{i}\langle |L_{v}|]\le L_{i}[|L_{j}…L_{v-1}|+1,|L_{j}…L_{v}|]$

$L_{t}\langle |L_{i}|-|L_{j}…L_{t-1}| ]\le L_{i}\langle |L_{i}|-|L_{j}…L_{t-1}|]<L_{i}[|L_{j}…L_{t-1}|+1\rangle$ 。

若不存在 $t$ 同理，证毕。

这个证明就很好的反映了 $\mathrm{Lyndon}$ 串的性质。

例题

1. 板子题

题目链接：https://www.luogu.com.cn/problem/P6114

题目大意：求 $\mathrm{Lyndon}$ 分解。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
void get_char_array(char *s){
    static char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
char st[N];
int n;
int main(){
    get_char_array(st);
    n = strlen(st + 1);
    int ans = 0;
    for(int i = 1; i <= n;){
        int j = i + 1, k = i;
        for(; j <= n && st[k] <= st[j]; j++){
            if(st[k] < st[j]) k = i;
            else k++;
        }
        for(; i <= k; i += j - k) ans ^= i + j - k - 1;
    }
    cout << ans << "\n";
    return 0;
}

2. 求最小表示法

求一个串的最小表示法。

做法

我一开始在想能不能只通过一个串的 $\mathrm{Lyndon}$ 分解得到最小表示法，后面发现不行，思考为什么，会发现原因和不能只通过单串的后缀数组得到最小表示法一样，就是循环位移字符串的不等式，不等价于后缀的不等式。

因此，这个题目不太能用单串的 $\mathrm{Lyndon}$ 分解来做。

具体做法为：求 $SS$ 的 $\mathrm{Lyndon}$ 分解，然后从 $\le |S|$ 的最后一个 $\mathrm{Ly}$ 串的开头开始就是最小表示法。（用性质 13 和 $\mathrm{Ly}$ 的性质不难证明这是对的）

3. 求每个前缀的最小后缀

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=6761

题目大意：求所有前缀的字典序最小的后缀。

证明

首先，给你一个串，怎么求它的最小后缀，显然是最后一个 $\mathrm{Ly}$ 串。

但是怎么求前缀的最后一个 $\mathrm{Ly}$ 串呢？

假设现在在求前缀 $i$ 的答案，答案数组是 $f$ 数组（记录最小后缀长度）。

根据 $Duval$ 算法的性质，我们只关心这个位置近似 $\mathrm{Ly}$ $T=L^t\overline{L}$ 。

如果 $T=L$ ，那么答案就是 $L$ 。

否则注意到，这个 $T$ 的 $\mathrm{Lyndon}$ 分解是 $L^t$ 拼接上 $\overline{L}$ 的$\mathrm{Lyndon}$ 分解，也可以看作是 $L$ 拼接上 $L^{t-1}\overline{L}$ 的 $\mathrm{Lyndon}$ 分解，所以可以看作求 $L^{t-1}\overline{L}$ 的最小后缀，注意到这等于 $f[i-|L|]$ ，做完了。

时间复杂度：$O(n)$ 。

代码的 $f$ 记录的是位置，魔改了一下上面的结论。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 2e7 + 5;
void get_char_array(char *s){
    static char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
void mnsuf(char *s, int *mn, int n){
    for(int i = 1; i <= n;){
        int j = i + 1, k = i; mn[i] = i;
        for(; j <= n && s[k] <= s[j]; j++){
            if(s[k] < s[j]) mn[j] = k = i;
            else mn[j] = mn[k] + j - k, k++;
        }
        for(; i <= k; i += j - k);
    }
}
char st[N];
int n, f[N];
int main(){
    cin.sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        get_char_array(st);
        n = strlen(st + 1);
        mnsuf(st, f, n);
        int ans = 0;
        for(int i = n; i >= 1; i--) ans = (ans * 1112ll + f[i]) % mod;
        cout << ans << "\n";
    }
    return 0;
}

4. 求每个前缀的最大后缀

这个没找到题目，直接口胡了。

做法

怎么求出一个串的最大后缀。

先把所有字母的偏序关系倒过来，近似的变为最小后缀，但是虚空大小无限大而不是无限小。

注意到，如果 $S=L_{1}L_{2}^{t_2}…L_{k}$ ，显然答案一定是 $L_{i}…L_{k}$ 。

注意到对于一个字符串链 $S_{1}\le S_{2}\le S_{3}…\le S_{t}$ ，如果存在 $i$ 满足：$S_{i} < S_{i+1}$（ $<$ 由于字符不同产生），那么 $S_{i} < S_{j} , j > i$（ $<$ 由于字符不同产生），也就是说，对于这个字符串链，如果我们认为虚空大小无限大，那么最小字符串应该是最小的 $S_{i}$ 满足：$\forall 1\le j<i,S_{j}$ 是 $S_{j+1}$ 的前缀，而且 $S_{i}$ 不是 $S_{i+1}$ 的前缀。

设 $S_{i}=L_{k-i+1}…L_{k}$ ，那么答案是什么就显然了。

问题来了，有没有等价的、更好用的说法呢？

我们设 $S=L_{1}^{t_1}…L_{p}^{t_{p}}$ （把相同的 $\mathrm{Ly}$ 合并）。

显然，如果 $L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 是 $L_{i}L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 的前缀，那么 $L_{i}^{o-1}L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 是 $L_{i}^{o}L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 的前缀 。

所以只需要考虑 $L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 是不是 $L_{i}L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 的前缀就行了。

根据性质 13 的证明可以得到，$L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 是 $L_{i}L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 当且仅当 $L_{i+1}^{t_{i+1}}…L_{k}^{p_{k}}$ 是 $L_{i}$ 的前缀。

所以可以得到，答案是 $L_{i}^{t_{i}}…L_{i}^{t_{p}}$ ，其中 $i$ 是最大的满足：$L_{i}^{t_{i}}…L_{p}^{t_{p}}$ 不是 $L_{i-1}$ 前缀的数字。

注意到，答案等价于最后一个位置在 Duval 算法中，第一次被近似 $\mathrm{Ly}$ $T$ 覆盖时的 $T$ 。

原因是 Duval 算法每次实际上是一次性添加：$L_{u}^{t_{u}}$ ，所以当 $i$ 恰好在 $L_{ans}^{t_{ans}}…L_{p}^{t_{p}}$ 的左端点时，根据前面的假设可以知道，此时 $j$ 一定在 $|S|$ ，也就是最后一个位置。（这里的 $i,j$ 表示代码中的 $i,j$ ）

而当 $j$ 第一次到 $|S|$ 时，$T$ 对应的 $L_{u}^{t_{u}}…L_{p}^{t_{p}}$ 满足 $L_{u+1}^{t_{u+1}}…L_{p}^{t_{p}}$ 是 $L_{u}$ 的前缀，只需要证明对于 $\forall v>u$ ，仍然满足这个性质就行了，一个显然的事情是，既然后面是 $L_{u}$ 的前缀，那么下一次跑的时候 $j$ 一定能跑到 $n$ ，类似跑 $L_{u}$ 的过程，归纳下去即可证明（即每次跳出内层循环的 $j$ 一定是不降的）。

扩展

其实注意到，$L_{u+1}^{t_{u+1}}…L_{p}^{t_{p}}$ 是 $L_{u}$ 的前缀 $\Leftrightarrow$ 生成 $L_{u}^{t_{u}}$ 时 $j=n$ ，根据上面的证明可以证得满足这样的 $u$ 是一个后缀，即存在 $u_{limie}$ 满足 $u\ge u_{limie}$ ，$L_{u+1}^{t_{u+1}}…L_{p}^{t_{p}}$ 是 $L_{u}$ 的前缀，如果 $u<u_{limit}$ ，则不满足。

进一步的有满足 $L_{u+1}^{t_{u+1}}…L_{p}^{t_{p}}$ 是 $L_{u}L_{u+1}^{t_{u+1}}…L_{p}^{t_{p}}$ 前缀的是一个区间。

由于 $U$ 是 $V$ 的前缀 $\Leftrightarrow$ $AU$ 是 $AV$ 的前缀。

所以设 $S=L_{1}…L_{k}$ ，则存在 $i_{limit}$ ：$\forall i\ge i_{limit}$ ，$L_{i+1}…L_{k}$ 是 $L_{i}L_{i+1}…L_{k}$ 的前缀，$i<i_{limit}$ 不是。

也就是说这样构造的字符串链的前缀关系是特殊的。

所以，上面的答案是 $L_{i}^{t_{i}}…L_{i}^{t_{p}}$ ，其中 $i$ 是最大的满足：$L_{i}^{t_{i}}…L_{p}^{t_{p}}$ 不是 $L_{i-1}$ 前缀的数字。

可以改成最小的 $i$ 满足：$L_{i+1}^{t_{i+1}}…L_{p}^{t_{p}}$ 是 $L_{i}$ 前缀的数字。

求前缀的答案的话，只需要在第一次跑到的时候更新一下就行了，时间复杂度：$O(n)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
void get_char_array(char *s){
    static char ss[N];
    cin >> ss;
    memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
void mxsuf(char *s, int *mx, int n){
    for(int i = 1; i <= n;){
        int j = i + 1, k = i; !mx[i] ? mx[i] = i : 0;
        for(; j <= n && s[k] <= s[j]; j++){
            !mx[j] ? mx[j] = i : 0;
            s[k] < s[j] ? k = i : k++;
        }
        for(; i <= k; i += j - k);
    }
}
int n, f[N];
char st[N];
int main(){
    get_char_array(st);
    n = strlen(st + 1);
    mxsuf(st, f, n);
    for(int i = 1; i <= n; i++) cout << f[i] << " ";
    cout << "\n";
    return 0;
}

某种无意义的占位符，防止排版垮掉。

5. Lyndon 串良好的递归结构

题目链接：https://qoj.ac/contest/1893/problem/9729

题解在对应的赛后总结写了。

更多例题正在咕咕咕咕咕

Runs

例题

https://www.luogu.com.cn/problem/P6656

https://www.luogu.com.cn/problem/P6656

一个基本的求法

参考资料

command_block 的洛谷博客 ：https://www.luogu.com/article/d4y3zqqv

OIwiki ：https://oi-wiki.org/string/lyndon/

国家集训队 2021 年论文：《胡昊 浅谈Lyndon分解》