Lyndon 词和 Runs

· · 算法·理论

cnblogs 链接

\text{Part 0:} 约定

本文中的字符串均为 0-\text{index}。

$s \prec t$ 表示在结束前 $s,t$ 这两个字符串就已经比出了字典序大小。 ## $\text{Part 1: Lyndon}$ 词 定义 $1$：称一个字符串 $s$ 为 $\text{Lyndon}$ 词当且仅当对于所有的 $i > 0$，均有 $s < s[i:] + s[:i]$。 定义 $2$：称一个字符串 $s$ 为 $\text{Lyndon}$ 词当且仅当对于所有的 $i > 0$，均有 $s < s[i:]$。 那么我们此时来证明为什么这两个定义是等价的。 先考虑从二推一，假设 $s < s[i:]$，那么因为 $s[i:]$ 的长度比 $s$ 短，所以肯定在结束前就比出了大小。而因为在结束之前就比出了大小，所以 $s < s[i:] + t$，所以我们就有 $s[i:] + s[:i]$。 接下来考虑一推二。假设 $s < s[i:] + s[:i]$，那么我们根据第一个不同的位置分类讨论。 1. 第一个不同的位置在 $s[i:]$ 中，那么显然是正确的。 2. 第一个不同的位置不在 $s[i:]$ 中，我们可以得知 $s[i:] = s[:|s| - i]$，而 $s[:i] \succ s[|s| - i:]$。因为 $s[:i]$ 和 $s[|s| - i:]$ 的长度相同，所以在结束前就比出了大小，那么我们可以得出 $s[:i] + s[i:] \succ s[|s| - i:] + s[:|s| - i]$，但是这个和定义矛盾了。所以只能在前面出现不同。 $\text{Lyndon}$ 词的一个性质就是若 $u,v$ 均为 $\text{Lyndon}$ 词且 $u < v$，则 $u + v$ 也是 $\text{Lyndon}$ 词。 接下来考虑怎么证明这个性质：根据定义，我们就是需要证明 $u + v$ 的所有非平凡后缀都大于 $u + v$。我们可以将这些非平凡后缀分成三类。 首先是形如 $u[i:] + v$ 的后缀，其中 $i > 0$。由于 $u$ 是一个 $\text{Lyndon}$ 词，因此 $u < u[i:]$。由于 $u[i:]$ 的长度小于 $u$，因此肯定在结束之前就比较出了大小，也就是说 $u \prec u[i:]$。因此，在后面拼上字符串 $v$，我们仍然有 $u + v \prec u[i:] + v$。 接下来是 $v$ 整体作为一个后缀。我们知道 $u < v$，可以进一步分两种情况讨论： 1. 如果 $u \prec v$，那么在后面拼上字符串，我们仍然有 $u + v \prec v$。 2. 否则，就意味着 $u$ 是 $v$ 的前缀，因此 $u + v$ 和 $v$ 的前 $|u|$ 个字符是一样的，需要继续比较 $v$ 和 $v[|u|:]$。由于 $v$ 是一个 $\text{Lyndon}$ 词，因此 $v \prec v[u[:]]$，于是仍然有 $u + v \prec v$。 最后，考虑形如 $v[i:]$ 的后缀。我们之前已经证明 $u + v \prec v$，结合 $v$ 是一个 $\text{Lyndon}$ 词，有 $v < v[i:]$，于是综合一下就有 $u + v < v[i:]$。 此时我们引出 $\text{Lyndon}$ 分解这一概念：若对于一个字符串 $s$，其存在一个序列 $w_0,w_1,\cdots w_{k-1}$，使得 $s = w_0 + w_1 + \cdots + w_{k-1}$ 且 $w_0 \ge w_1 \ge \cdots \ge w_{k-1}$ 同时这 $k$ 个字符串均为 $\text{Lyndon}$ 词，则称这个分解为 $s$ 的 $\text{Lyndon}$ 分解。 此时我们引出一个 $\text{Lemma}:$ 每一个字符串的 $\text{Lyndon}$ 分解唯一。 考虑怎么证明。可以先证明存在性，假设我们先不管 $w_0 \ge w_1 \ge \cdots \ge w_{k-1}$ 这个条件，那么我们我们肯定有一个 $\text{Lyndon}$ 分解就是每一个字符作为一段。如果此时这个分解已经满足了条件，那么就不用管了。否则肯定存在一个 $i$ 满足 $w_i < w_{i + 1}$，那么把这两个 $\text{Lyndon}$ 词合并在一起即可。 然后我们就发现把所有操作做完之后剩下的就是一个合法的 $\text{Lyndon}$ 分解了。而上面的内容也给我们提供了一个 $\mathrm O(n \log n)$ 的 $\text{Lyndon}$ 分解方法。 接下来考虑证明唯一性。此时我们发现一个字符串 $s$ 其 $\text{Lyndon}$ 分解的第 $i$ 个词 $w_i$ 是 $s$ 的后缀中字典序在 $w_{i+1} + w_{i + 2}+\cdots+w_{k - 1}$ 之前的后缀 $s[m_i:]$ 的前缀。那么这个时候因为后面的 $w$ 已经确定了，而后缀 $s[m_i:]$ 是唯一的，所以 $w_i$ 此时也是唯一的。 我们这个时候是从后缀的角度来观察 $\text{Lyndon}$ 分解。那么我们可以考虑从前缀的角度来观察 $\text{Lyndon}$ 分解：对于任意 $s$，其 $\text{Lyndon}$ 分解的第 $i$ 个词 $w_i$ 是以 $w_i$ 为开头的 $s$ 的后缀的最长的 $\text{Lyndon}$ 前缀。 或者说如果 $u$ 是 $s$ 的最长 $\text{Lyndon}$ 前缀，这 $s[|u|:]$ 是第一个小于 $s$ 的后缀。 首先考虑若对于 $i < |u|$，是否必定有 $s[i] > s$。由于 $u = s[:|u|]$ 是 $\text{Lyndon}$ 词，因此 $s[:|u|] \prec s[i:|u|]$，从而必然有 $s < s[i:]$。 接下来考虑 $s[|u|:]$。对 $s$ 做 $\text{Lyndon}$ 分解，得到 $w_0,\cdots,w_{k-1}$，其中 $u = w_0$。为了简便起见，我们认为 $i \geq k$ 时，$w_i$ 是空串。 假设 $w_0 = \cdots = w_{i-1} > w_i$，即 $w_i$ 是 $\text{Lyndon}$ 分解中第一个小于 $w_0$ 的词。那么比较 $s = w_0 + \cdots + w_{k-1}$ 和 $s[|u|:] = w_1 + \cdots + w_{k-1}$，不同从 $s$ 的 $w_{i-1}$ 和 $s[|u|:]$ 的 $w_i$ 开始。此时分两种情况讨论： 1. 如果 $w_{i-1} \succ w_i$，那么在结束前就比较出了大小，有 $s > s[|u|:]$。 2. 否则，$w_i$ 是 $w_{i-1}$ 的一个前缀。接下来继续比较 $w_{i-1}$ 的某个后缀 $w_{i-1}[j:]$ 和 $w_{i+1}$。若 $w_{i+1}$ 已是空串，则比较出了大小。 3. 否则，假设 $w_{i+1} \geq w_{i-1}[j:]$，则有 $w_{i+1} \geq w_{i-1}[j:] > w_{i-1}$，矛盾，故 $w_{i+1} < w_{i-1}[j:]$。若 $w_{i+1} \prec w_{i-1}[j:]$，则比较出了大小。 4. 否则，$w_{i+1}$ 是 $w_{i-1}[j:]$ 的一个严格前缀，继续比较 $w_{i-1}[j+k:]$ 和 $w_{i+2}$，以此类推，最终要么比较出了大小，要么继续推到下一位。 那么我们一定可以比出大小。并且有 $s > s[|u|:]$。 此时我们来考虑一个 $\text{Lyndon}$ 词到底会长什么样。 假设一个 $\text{Lyndon}$ 词的最长 $\text{Lyndon}$ 前缀为 $u$，则我们有 $s = u^k + u[:i] + c$，其中 $c$ 是一个字符且 $c > u[i]$。 这个东西的证明我们可以考虑使用归纳法。假设我们已经确定了前缀是一个 $u^k + u[:i]$，然后此时看下一个位置是什么： - 如果 $c < u[i]$，那么 $u[:i] + c \prec u$，那么 $s$ 就一定不是一个 $\text{Lyndon}$ 词。 - 如果 $c = u[i]$，那么直接继续。 - 如果 $c > u[i]$，那么此时的 $s$ 就已经是一个 $\text{Lyndon}$ 词了，所以接下来怎么扩张都一定会使得 $u$ 不再是最长的 $\text{Lyndon}$ 前缀了，所以在这个时候就一定会停止。 根据这个定理我们就有一个更加精妙的 $\text{Lyndon}$ 分解做法了。 首先我们从最基础的 $\text{Lyndon}$ 词，也就是单个字符 $u = s[0]$ 开始。我们不断往后扫描下一个字符，如果能够符合 $k \cdot u + u[:i]$ 的形式，就一直继续。直到遇到第一个不复读的字符 $c$。 如果 $c > u[i]$，则 $u^k + u[:i] + c$ 就是一个更长的 $\text{Lyndon}$ 词，令 $u$ 更新为 $u^k + u[:i] + c$，继续往后扫描。 否则，如果 $c < u[i]$，或者没有下一个字符了，根据之前的分析，后面再接任何内容都不可能得到一个 $\text{Lyndon}$ 词，因此，$u$ 就是最长的 $\text{Lyndon}$ 前缀，也就是 $w_0$。后续的部分仍然找最长的 $\text{Lyndon}$ 前缀，如果 $u$ 完整重复了 $k$ 次，同理剩下的 $k - 1$ 个 $u$ 也都是最长的 $\text{Lyndon}$ 前缀，可以逐一加入 $\text{Lyndon}$ 分解中。 最后，我们还剩下 $u[:i] + c$ 的部分，由于 $c < u[i]$，这部分已经丧失了 $\text{Lyndon}$ 词的性质，我们需要废弃已解析的部分，重新以其第一个字符作为 $u$，重新开始前述的解析过程。 然后我们就可以发现这个算法是线性的。 ## $\text{Part 2. Runs}

我们称 p 为 s 的一个周期当且仅当对于所有的 0 \le i < |s| - p 均有 s[i] = s[i+p]。一个更加直观的表示就是令 u = s[:p]，若 s 可以表示为 u^k + u[:i] 其中 k \ge 1,i < p 那么我们称 p 为 s 的一个周期。

此时我们引出一个定理（弱周期定理）：若 p,q 均为 s 的周期，且 p + q \le |s|，则 \gcd(p,q) 也是 s 的周期。

那么我们此时定义一个周期 p 为 s 的半周期为 2p \le |s|。而如果一个 s 存在一个半周期，那么肯定存在一个最小半周期使得 s 的所有半周期都是这个半周期的倍数。

此时定义 (i,j,k) 为一个字符串 s 的一个 \text{Run} 满足子串 s[i:j] 包含 k 这个最小半周期且向外扩张之后无法保持这个半周期。而 \text{Runs} 为 s 的所有 \text{Run} 组成的集合。

但是 \text{Run} 的个数并不好直接估计上界，所以我们考虑引入一个概念：称 (i,j,k) 为一个字符串 s 的一个若 \text{Run} 满足子串 s[i:j] 包含 k 这个半周期且向外扩张之后无法保持这个半周期。这个定义和 \text{Run} 的区别就在弱 \text{Run} 不要求 k 是最小半周期。

为了分析弱 \text{Run} 的数目，我们根据不同的 p 进行分类，检查一下一个长度为 n 的字符串 s 中最多有多少个具有半周期 p 的弱 \text{Run}。

首先，我们将字符串 s 每 p 个分为一段，最后不足 p 个的直接丢弃，得到 t_i = s[ip:(i+1)p]，其中 m = \lfloor \frac{n}{p} \rfloor。

由于具有半周期 p 的弱 \text{Run} 长度至少为 2p，容易证明，它至少完整地包含一个段 t_i。

对于 t_i 来说，一个弱 \text{Run} 要包含它，则左右两端必然是不断复读 t_i，直到无法再复读为止。如果扩张得到的长度不小于 2p，则得到了一个弱 \text{Run}；容易验证，这样的弱 \text{Run} 是唯一的，也就是说，至多只有一个弱 \text{Run} 包含 t_i。

这样，每个 t_i 对应至多一个弱 \text{Run}，因此具有半周期 p 的弱 \text{Run} 的数目至多为 \lfloor \frac{n}{p} \rfloor。

那么，所有弱 \text{Run} 的数目至多为 \sum_{p=1}^n \lfloor \frac{n}{p} \rfloor，根据调和级数，这个和的数量级是 O(n \log n)。

那么我们可以获得一个求弱 \text{Runs} 的做法了：先枚举 p，然后从前往后扫每一个段 t_i = s[ip:(i+1)p]。然后求出 s[:ip] 和 s[:(i+1)p] 的最长公共后缀和 s[ip:] 和 s[(i+1)p:] 的最长公共前缀就可求出最多可以向外拓展多少了。结合 SA 可以做到 \mathrm O(n \log n)。然后求 \text{Run} 就可以直接对于所有的 (i,j) 只保留最小的 p 即可。

为了降低我们得到的 \text{Run} 的个数的上界，我们需要引出一个引理：

对于一个长度为 n 的字符串，其 \text{Run} 的数量最多为 2n。

对于证明，我们考虑一个 \text{Run}(i,j,p)，令 t = s[i:i+p]，那么 t 一定是一个本原串。那么我们考虑 t 的一个特殊循环 t^{\prime} = t[k:]+t[:k]，而且 t^{\prime} 是一个 \text{Lyndon} 词。

那么此时我们关注这个无法再扩张的 j，而不能扩张的原因是下一个字符 c 和 t^{\prime} 中对应的位置 c_0 并不相同。那么此时我们先假设 c < c_0，那么此时从 t^{\prime} 开始的位置到 j 的字符串应该就形如 {t^{\prime}}^k + t^{\prime}[:l] + c 的结构，而这个字符串恰好是一个 \text{Lyndon} 词，且是以 t^{\prime} 开始位置为开头的最长 \text{Lyndon} 前缀。

那么 c < c_0 这个情况的 \text{Run} 数量至多 n。此时我们可以把字符反转一下，那么此时统计的就是 c > c_0 的情况了，而这个情况也最多 n 个。所以 \text{Run} 的数量最多 2n。

那么根据上面的过程，我们可以知道一个新的求 \text{Runs} 的方法：对于每一个位置 i 求出最长的 \text{Lyndon} 前缀 t_i，然后尽可能地向两边扩张，如果扩张的长度超过 2|t_i|，那么就得到了一个新的 \text{Run}。然后再反转一次后再做一次即可。

此时我们定义一个 \text{Run}(i,j,p) 的指数为 e = \frac{j-i}{p}，那么对于一个长度为 n 的字符串，其所有 \text{Run} 的指数和在 \mathrm O(n) 级别。这个证明和上一个类似，这里就不证明了。