摘抄自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}$串）

方法二：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：感覺這個算法就只能考論文題。。。太惡心了。。。