【学习笔记】lyndon分解

摘抄自quack的ppt。

这部分和$sa$的关联比较大，可以加深对$sa$的理解。

Part 1

如果字符串$s$的字典序在$s$以及$s$的所有后缀中是最小的，则称$s$是一个$\text{lyndon}$串。

$\text{lyndon}$分解，指的是把一个字符串分成若干段，每一段都是一个$\text{lyndon}$串，问最少的分割段数。

方法一：用后缀数组，$sa[1]$就是$\text{lyndon}$分解的最后那一段，$\text{lyndon}$分解倒数第二段就是把$sa[1]$那一段排除之后排的最靠前的$sa$，以此类推。

$sa$可以用来$\text{lyndon}$分解依赖于以下结论：

定义数组$a[i]$为最小的$j$，使得$j>i$且$S[j:|S|?1]<S[i:|S|?1]$，如果不存在这样的$j$，可以认为$a_i=|S|$。

那么，$S$的$\text{lyndon}$分解的第一项为$S[0:a[0]?1]$，且后面$m?1$项就是$S[a[0]:|S|?1]$的$\text{lyndon}$分解。

证明：显然此时不能划分到$a[0]$之后，否则可以根据原串后缀的信息道出矛盾。因此只需论证划分到$a[0]$合法即可。注意到此时$S[a[0]]\le S[0]$，因此对于任意$j\in [1,a[0]?1]$，一定满足$S[0:a[0]?j?1]\ne S[j:a[0]?1]$，又因为$sa[0]<sa[j]$，因此$S[0:a[0]?1]$一定是它的所有后缀当中最小的。

基本性质：

$1.1$ 若字符串$u,v$是$\text{lyndon}$串且$u<v$，则$uv$是$\text{lyndon}$串。

$1.2$ 若字符串$s$是$\text{lyndon}$串，$s^{\prime }a$是$s$的前缀，那么$s^{\prime }b(b>a)$是$\text{lyndon}$串。（注意$s^{\prime }a$不一定是$\text{lyndon}$串）

$1.3$ 若$u,v$是任意串，$u<w$，$v<w$，$w$是$\text{lyndon}$串，则$uv<w$（ [JSOI2019] 节日庆典 ）

方法二：duval 算法

每次维护一个前缀的$\text{lyndon}$分解。这个前缀$S[1:k?1]$可以被分解成$s_1,...,s_g$这些$\text{lyndon}$串和$S[i:k?1]$这个近似$\text{lyndon}$串（形如$w^k{w}^{\prime }$，$w$是一个$\text{lyndon}$串，$w^{\prime }$是$w$的前缀）。

具体的，三个变量$i,j,k$维持一个循环不变式：

• $S[0:i?1]=s_1{s}_2...s_g$ 是已经固定下来的分解，满足$s_l$是$\text{lyndon}$串，且$s_l\ge s_{l+1}$（否则可以合并）。
• $S[i:k?1]=t_1{t}_2...t_{h}v$是没有固定的分解，满足$t_1$是$\text{lyndon}$串，$t_1=t_2=...=t_h$，$v$是$t_h$的（可为空的）真前缀，令$j=k?|t_1|$。

复杂度为$O(n)$。比sa快啊

代码

Part 2

$\text{lyndon}$分解的应用：

$1.3$ 给定长为$n$的字符串$S$，求出$S$的最小表示法。

方法：将$SS$ $\text{lyndon}$分解，找到分解后最后一个字符串，它的首字符为$SS[p]$，且$p\in [0,|S|)$。可以证明$SS[p:p+|S|?1]$是字典序最小的。（运用第一条引理，转化为比较在原串中的后缀，即sa）

$1.4$ 给定长度为$n$的字符串$S$，将$S$分为最多$k$个串$c_1{c}_2...c_k$，求$\max c_i$的最小值。

方法：看到字典序，容易想到$\text{lyndon}$分解。首先把$S$ $\text{lyndon}$分解成$s_1,...,s_g$，如果$k\ge g$，那么答案即为$s_1$；否则，如果$s_1>s_2$，那么显然可以分成$s_1$和剩下的所有串，答案还是$s_1$。因此，考虑分解成$s_1^m{s}_g$的情况，如果$k>m$，那么答案还是$s_1$，如果$k\le m$，那么尽量均分一下即可。

推广：多次询问，每次询问$S$的一段后缀的答案。

考虑求出原串的sa数组，显然可以求出第一项以及重复次数（可以用哈希），这样就做完了。

$1.5$ 求$S$的每个前缀的字典序最小的后缀

首先把$S$ $\text{lyndon}$分解成$s_1,...,s_g$，显然$s_1...s_k$的字典序最小的后缀是$s_k$。但是前缀取到分解出来的$\text{lyndon}$串半截时，答案可能不一样。

考虑$\text{duval}$算法求$\text{lyndon}$分解的过程，分类讨论：

• 若$s[k]>s[j]$，此时$ans[k]$应该等于$i$，因为$s[i:k]$构成一个新的$\text{lyndon}$串
• 若$s[k]=s[j]$，此时$ans[k]=ans[j]+k?j$
• 若$s[k]<s[j]$，在$\text{lyndon}$串开头时更新

$1.6$ 求$S$的每个前缀的字典序最大的后缀

首先把字符比较反过来，然后要尽量向左取，当$s[k]\le s[j]$的时候，$s[i:k]$这一段都保持了是一个近似$\text{lyndon}$串，所以都取近似$\text{lyndon}$串的左端点$i$作为答案即可。

ps：感觉这个算法就只能考论文题。。。太恶心了。。。