lgswdn-SA > Lyndon and runs

Lyndon and runs

2026-07-12

string

Lyndon 串

Definition

Lyndon 串：

  • 定义 Lyndon 串为字典序小于其每个真后缀的字符串.

Lyndon 分解：

  • 将字符串拆解成 \(w=w_1w_2\dots w_k\)，并满足 \(w_i\) 为 Lyndon 串，\(w_i\ge w_{i+1}\) 的形式称为 Lyndon 分解.
  • 称 \(w_i\) 为 \(w\) 的 Lyndon 因子.

Necklace：

  • 定义 Necklace 为满足字典序小于等于其所有循环表示的字符串.

性质：

  • 对于 \(w\) 的 Lyndon 分解，有 \(w_k\) 为 \(w\) 的最小真后缀.

    Proof：若最小真后缀为 \(uw_i\dots w_k\)，则其 \(\ge w_{i-1}w_i\dots w_k\ge w_k\).

    推论：Lyndon 分解唯一.

  • 若 \(u,v\) 都为 Lyndon 串，\(u>v\)，则 \(uv\) 也为 Lyndon 串.

    Proof：显然.

    推论：结合前一个性质，知 Lyndon 分解存在.

  • \(w_i>w_{i+1}^{\infty}\)

    Proof：若 \(w_{i+1}\) 不为 \(w_i\) 前缀则显然；否则由于 \(w_{i+1}\) 为 Lyndon 串所以任何后缀都大于其自身，故所以仍然 \(>w_{i+1}\)，故 \(w_i>w_{i+1}^{\infty}\).

Duval's Algorithm

对于 Lyndon 串 \(w\)，定义形如 \(w^kw'\) 的串为一个近似 Lyndon 串，其中 \(w'\) 为 \(w\) 的前缀.

Duval 算法一边从前往后加字符一边进行分解：

  • 假设当前已经加入到了第 \(i\) 个字符，并且 \(w[1,i]\) 可以分解为若干个 Lyndon 因子加上一个近似 Lyndon 串 \(w[j,i]=u^tu'\)，\(|u|=k\). 该近似 Lyndon 串也满足 Lyndon 串的递减条件.
  • 考虑新加入的字符 \(w_{i+1}\)：
    • \(w_{i+1}=w_{i+1-k}\)，则加入后仍然保持相同的近似 Lyndon 串结构，不需要做改变.
    • \(w_{i+1}>w_{i+1-k}\)，则 \(w[j,i+1]\) 为 Lyndon 串，设 \(u\leftarrow w[j,i+1]\)，即 \(k\leftarrow i-j+2\) 即刻.
    • \(w_{i+1}<w_{i+1-k}\)，则 \(u'w_{i+1}<u\). 于是这 \(t\) 个 \(u\) 即为 Lyndon 因子，将其分解出来. 然后我们将 \(i\) 回退到 \(u '\) 的开始，再做一遍.

正确性容易验证. 复杂度需要考虑其回退问题：每当分解出一个 Lyndon 因子 \(u\)，\(i\) 就会减少 \(\le |u|\) 的距离. 于是 \(i\) 最多减少 \(n\) 次，故总复杂度 \(O(n)\).

Significant Suffix

Significant Suffix：

  • 对于后缀 \(w'\)，若存在字符串 \(u\) 使得对于任意后缀 \(w''\) 皆有 \(w'u<w''u\)，则称 \(w'\) 为一个 significant suffix.
  • 字符串的所有 significant suffix 的集合称为其最小后缀组 \(SS(w)\).

性质：

  • 若有后缀 \(u^2v\)，则 \(uv\not\in SS(w)\).

    Proof：显然 \(u^2v,uv,v\) 中，\(uv\) 不是 significant 的.

    推论：对于 Lyndon 分解 \(w=w_1^{c_1}\dots w_k^{c_k}\)，任何一个 significant suffix 一定形如 \(w_i^{c_i}\dots w_k^{c_k}\).

  • 对于 \(u,v\in SS(w)\)，\(|u|<|v|\)，则 \(u\) 为 \(v\) 的 border 且 \(2|u|\le |v|\).

    Proof：首先由于 \(u,v\) 的比较不会在前 \(|u|\) 位结束，故知其为 Border；另一方面，若 \(2|u|>|v|\)，那么就会产生周期，于是由上一个性质知，\(u\not\in SS(w)\).

    推论：\(|SS(w)|= O(\log n)\).

为了求解 \(SS(w)\)，我们需要先证明以下性质：

  • 记 \(s_i=w_i^{c_i}\dots w_k^{c_k}\)，则 \(s_{i+1}\) 为 \(s_{i}\) 前缀的充分必要条件为 \(s_{i}\) 在 Duval 算法的过程中可以形成近似 Lyndon 串；换句话说，令 \(\lambda\) 为第一次匹配到字符串末尾时的近似 Lyndon 串，则有 \(i\ge \lambda\).

    Proof：必要性：如果没能形成一个到末尾的近似 Lyndon 串，意味着匹配的时候出现了不等号，所以显然不是 border；充分性：近似 Lyndon 串的结构 \(w_i^{c_i}s_{i+1}\) 满足 \(s_{i+1}\) 为 \(w_i\) 的前缀，故显然充分.

    推论：只有 \(i\ge \lambda\) 的 \(s_i\) 才可能 \(\in SS(w)\).

然后对于 \(i\ge \lambda\) 考察如下引理：

  • 记 \(w_i=s_{i+1}y_i\)，\(x_i=y_is_{i+1}\)，于是 \(s_i=w_i^{c_i}s_{i+1}=s_{i+1}x^{c_i}\).

  • 引理：\(y_i>x_{i+1}^{\infty}\).

    Proof：\(s_{i+1}x_{i+1}^{\infty}=s_{i+1}(y_{i+1}s_{i+2})^{\infty}=(s_{i+2}y_{i+1})^{c_{i+1}}s_{i+2}(y_{i+1}s_{i+2})^{\infty}=w_{i+1}^{\infty}\)，而 \(w_{i+1}^{\infty}< w_i=s_{i+1}y_i\)，故得证.

    推论：\(x_{i}^{\infty}\ge y_i> x_{i+1}^{\infty}\)，即 \(\{x_i^{\infty}\}\) 为递降的序列.

最终结论：\(s_i\in SS(w)\) 的充分必要条件是 \(i\ge \lambda\).

  • Proof：考虑将 \(s_iv\) 写成 \(x_k^{c_k}x_{k-1}^{c_{k-1}}\dots x_i^{c_i}v\) 的形式，于是知只要取 \(v>x_j^{c_j}(j\ge i)\)，以及 \(v<x_{i-1}^{c_{i-1}}\) 即刻. 由于 \(x^{\infty}\) 的单调性质，我们知这是可以做到的.

这也给我们了如下问题的解法：\(MinSuf(w,v)\) 表示求出一个 \(w\) 的后缀使得 \(wv\) 最小. 根据上面的结论，我们有：

  • \(v>x_{\lambda}^{\infty}\)：\(MinSuf=s_{\lambda}\).
  • \(v\in (x_{i-1}^{\infty},x_i^{\infty})\)：\(MinSuf=s_i\).
  • 否则 \(MinSuf=\epsilon\).

Runs

Definition

本原串：没有整周期的串.

幂串：形如 \(w^k\)（\(k\ge 2\)）的串（\(k\) 次方串）. 若 \(w\) 为本原串，我们称其为本原 \(k\) 次方串.

性质：对于最小周期为 \(p\) 的串 \(S\)，任意子串 \(S[i,i+kp-1]\) 都是本原 \(k\) 次方串. 证明显然.

Runs：

  • 如果子串 \(S[i,j]\) 有最小周期 \(p\)（\(2p\le j-i+1\)），且是极长的（\(S_{i-1}\neq S_{i+p-1},S_{j+1}\neq S_{j-p+1}\)），那么称 \((i,j,p)\) 为字符串 \(S\) 的一个 run.
  • 对于 \(r=(i,j,p)\)，记 \(e_r=\frac{j-i+1}{p}\) 为该 run 的指数.

性质：

  • 任意两个周期相同的 run 的交都 \(<p\). （trivial）

  • 任意 run \((i,j,p)\) 可以导出 \(j-i+2-2p\) 个本原平方串，并且这些串不交地构成了所有本原平方串的集合.

    Proof：对于任意本原平方串我们都能扩展成一个 run；而由于交 \(<p\) 故不可能有两个 runs 共享同一个本原平方串.

Lyndon Root & Runs Theorem

定义在 \(<_0\) 下 \(0<1\)，\(<_{1}\) 下 \(1<0\). 注意 \(S<T\) 等价 \(T<S\) 不总是成立（反例为一个是另一个前缀）.

Lyndon 根：

  • 对于一种字典序 \(<_t\)（\(t\in\{0,1\}\)），在一个 run \(r=(i,j,p)\) 内部的子串 \(S [u,u+p-1]\)，若在 \(<_t\) 意义下 \(S[u,u+p-1]\) 为 Lyndon 串，则称其为 \(r\) 关于 \(<_t\) 的一个 Lyndon 根.
  • 定义真 Lyndon 根为 \(u\neq i\) 的 Lyndon 根.
  • 性质：任何 \(r\) 的真 Lyndon 根存在且字符串唯一（即最小表示）.

Lyndon 数组：

  • 定义 \(l_t(i)\) 为在 \(<_t\) 意义下，以 \(i\) 为左端点的最长 Lyndon 子串的右端点.

性质：

  • 以下皆假设 \(s\) 后面跟了一个 \(-1\) 字符.

  • \(l_0(i)\) 和 \(l_1(i)\) 至少有一个 \(=i\).

    Proof：令 \(j\) 为 \(i\) 后面第一个 \(s_i\neq s_j\) 的 \(j\). 不妨设 \(s_i<_0s_j\). 那么必然有 \(l_0<j\). 于是 \(l_0=i\).

  • 对于任意 run \(r=(i,j,p)\)，若 \(s_{j+1}<_t s_{j+1-p}\)，那么其任何 Lyndon 根都有 \(l_t(u)=u+p-1\).

    Proof：对于 \(v>j\)，由条件知 \(s[u,v]\) 显然不是 Lyndon 串；另一方面真近似 Lyndon 串显然也不是 Lyndon 串.

  • 对于任意 \(u\in[1,|S|]\)，\(S[u,l_0(u)]\) 和 \(S[u,l_1(u)]\) 不可能同时是真 Lyndon 根.

    Proof：不妨设 \(l_0(u)=u\)，则 \(S_{l_1(u)}\neq S_u\)；另一方面，由于 \(S[u,l_0(u)]\) 为真 Lyndon 根所以 \(S_u=S_{u-1}=S_{u+p_1-1}=S_{l_1(u)}\)，矛盾.

  • 任何两个不同 runs 的全部真 Lyndon 根的左端点不交.

    Proof：假设重合且为 \([u,x]\)，\([u,y]\)，则由上上条性质知 \(\{x,y\}=\{l_0(u),l_1(u)\}\)，与上一条性质矛盾.

Runs 定理：

  • 令 \(\rho\) 为 runs 数，\(\sigma\) 为 runs 指数之和，则 \(\rho<n\)，\(\sigma<3n\).

  • Proof：

    首先，一个 runs 至少有两个真 Lyndon 根，所以 \(\rho<n\).

    其次，若指数 \(=x\)，则至少有 \(\lfloor x-1\rfloor\ge x-2\) 个真 Lyndon 根，所以 \(\sigma <3n\).

Three Square Lemma

Three Square Lemma:

  • 若 \(u^2,v^2,w^2\) 是本原平方串，并且 \(u^2,v^2,w^2\) 依次为前者的前缀，则 \(|w|\ge |u|+|v|\).

Proof:

  • 若 \(|w|<|u|+|v|\)，则 \(|w|<2|v|\). 于是对于 \(i+|w|-|v|\le |v|\) 有 \(v_i=w_i=w^2_{i+|w|}=v_{i+|w|-|v|}\)，故 \(|w|-|v|\) 为 \(v\) 的周期.

  • 若 \(|v|>2|u|\)，则 \(|w|-|v|\) 也为 \(u^2\) 的周期，于是由弱周期引理知道 \(\gcd(|u|,|w|-|v|)\) 为 \(u^2\) 的整周期，与 \(u\) 为本原平方串矛盾. 故 \(|v|\le 2|u|\).

  • 若 \(|u|+(|w|-|v|)\le |v|\)，则由弱周期引理知 \(\gcd(|u|,|w|-|v|))\) 为 \(v\) 的整周期，也是 \(u\) 的整周期，同样矛盾. 故 \(|u|+|w|\le 2|v|\).

  • 于是我们目前在假设下得出了结论 \(|w|<|u|+|v|\)，\(\frac{|u|+|w|}{2}\le |v|\le 2|u|\).

  • 于是我们可以把 \(u^2,v^2,w^2\) 写成如下的形式：

    \(u^2:\) 1111122211111222

    \(v^2:\) 1111122233311111222333

    \(w^2\): 11111222333111111111122233311111

  • 于是可以发现 11111是222333的前缀，333是11111的前缀，所以333是222333的前缀，所以222是222333的周期；另一方面，222333是11111222的前缀，所以333是222333的周期，所以 gcd(222,333) 是 222333 的周期；另一方面，222是11111222的周期，所以 gcd(222,333) 是 \(u\) 的周期.

  • 然后由于 222 是 11111 的前缀，所以 11111 是 \(u\) 的周期. 然后就得到 gcd(11111,222,333) 是 \(u\) 的周期，并且小于 \(u\) 的整周期. 矛盾.