跳转至

Lyndon 分解

OI-Wiki 里的字符串板块有 这个,就学一学叭?

写在前面

为了更方便地描述字符串相关内容,我们做出以下规定:

  1. 字符串通常用 \(S, T\) 等表示,\(c\) 通常表示一个字符,\(\Sigma\) 表示字符集;
  2. 字符串长度用 \(\left|S\right|\) 表示;
  3. 字符集大小用 \(\left|\Sigma\right|\) 表示;
  4. \(S[l..r]\) 表示 \(S[l], S[l + 1], \ldots, S[r - 1], S[r]\)
  5. 空串用 \(\epsilon\) 表示;
  6. \(S\)\(T\) 的前缀,用 \(S \sqsubset T\) 表示;\(S\)\(T\) 的后缀,用 \(S \sqsupset T\) 表示;
  7. \(S\) 的字典序小于 \(T\),用 \(S < T\) 表示,即 \(\left|S\right| < \left|T\right| \lor (\left|S\right| = \left|T\right| \land \exists i \in [1, \left|S\right|), \textrm{s.t. }S[1..i] = T[1..i] \land S[i + 1] < T[i + 1])\)
  8. 一个字符串 \(S\) 重复 \(i\) 次形成的字符串,即 \(\begin{matrix}\overline{\underbrace{SS\cdots S}}\\S \textrm{ repeated } i \textrm{ times}\end{matrix}\),用 \(S^i\) 表示。

特殊地,本文的字符串下标 \(1\) 开始

一些字符串有关术语的例子

对于 \(S = \mathtt{ABCBAD}\) 而言:

  1. \(\left|S\right| = 6\)

  2. \(\left|\Sigma\right| = 4\)

  3. \(S[2..4] = \mathtt{BCBA}\)

Lyndon 串

定义

若一个字符串 \(S\) 满足 \(\forall i \in [2, \left|S\right|], S< S[i..\left|S\right|]\),则我们称这个字符串为一个「Lyndon 串」。

它的等价命题是 \(S\) 的字典序小于其所有 非平凡的 循环同构串。

性质

性质 1

若有两 Lyndon 串 \(S, T\),且 \(S < T\),则 \(\overline{ST}\) 也为 Lyndon 串。

证明

我们分两种情况来证明:

  1. \(\left|S\right| \ge \left|T\right|\)

    显然 \(\overline{ST} < T\),又有 \(T\) 的所有后缀都大于 \(T\),因此 \(\overline{ST}\) 的所有后缀都大于 \(\overline{ST}\)

    因此 \(\overline{ST}\) 是 Lyndon 串。

  2. \(\left|S\right| > \left|T\right|\)

    • \(S \not\sqsubset T\)

      此时 \(\overline{ST} < T\),由 1 即可得证。

    • \(S \sqsubset T\)

      \(\overline{ST} \ge T\),则有 \(T \ge T[\left|S\right| + 1..\left|T\right|]\),与「\(T\) 是 Lyndon 串」矛盾。

      那么此时一定有 \(\overline{ST} < T\),由 1 即可得证。

综上所述,若有两 Lyndon 串 \(S, T\),且 \(S < T\),则 \(\overline{ST}\) 也为 Lyndon 串。

性质 2

若字符串 \(S\) 和字符 \(c\) 满足存在某一个字符串 \(T\) 使得 \(\overline{Sc} \sqsubset T\),则 \(\forall c' > c \in \Sigma\)\(\overline{Sc'}\) 均为 Lyndon 串。

证明

不妨设 \(T = \overline{ScR}, n = \left|S\right|\),则 $$ \forall i \in [2, n], \overline{S[i..\left|S\right|]cR} > \overline{ScR} $$ \(\therefore \overline{S[i..\left|S\right|]c} \ge S\)

\(\therefore \overline{S[i..\left|S\right|]c'} > \overline{S[i..\left|S\right|]c} \ge S\)

\(\because c \ge S[1]\)

\(\therefore c' > c \ge S[1]\)

\(\therefore T = \overline{Sc'}\) 也是一个 Lyndon 串。

Lyndon 分解

将一个字符串 \(S\) 分解成 \(\overline{T_1T_2\cdots T_m}\),满足 \(\forall i \in [1, m), T_i \ge T_{i + 1}\),且 \(\forall i \in [1, m]\)\(T_i\) 均为 Lyndon 串。

这样的一个分解我们称之为「Lyndon 分解」。

定理

一个字符串 \(S\) 的 Lyndon 分解有且仅有一个。

证明
  1. 先证明存在性:

    假设我们有一个非 Lyndon 分解 \(S = \overline{R_1R_2\cdots R_x}\),初始化 \(x = n, \forall i \in [1, n], R_i = S[i]\)

    \(\exists i \in [1, n), \textrm{s.t. }R_i < R_{i + 1}\),则将 \(R_i\)\(R_{i + 1}\) 合成成一个字符串,这样一定能得到一个 Lyndon 分解。

  2. 再证明唯一性:

    \(S\) 有两个 Lyndon 分解 \(S = \overline{P_1P_2\cdots P_iP_{i + 1}\cdots P_x}\)\(S = \overline{P_1P_2\cdots P_iQ_{i + 1}\cdots Q_x}\)

    不妨令 \(\left|P_{i + 1}\right| > \left|Q_{i +1}\right|\),设 \(P_{i + 1} = \overline{Q_{i + 1}Q_{i + 2}\cdots Q_{k}Q_{k + 1}[1..l]}\),则 $$ P_{i + 1} < Q_{k + 1}[1..l] \le Q_{k + 1} \le Q_{i + 1} < P_{i + 1} $$ 与假设矛盾。

综上所述,一个字符串 \(S\) 的 Lyndon 分解有且仅有一个。

Duval 算法

算法流程

算法的核心思想是维持一个循环不变式:

  • \(S[1..i - 1] = \overline{R_1R_2\cdots R_w}\) 是固定下来的 Lyndon 分解,也就是 \(\forall l \in [1, w], R_l\)\(\textrm{Lyndon}\) 串且 \(R_l > R_{l + 1}\)
  • \(S[i..k-1] = T ^ \alpha + Z (\alpha > 1)\) 是没有固定的分解,满足 \(T\)\(\textrm{Lyndon}\) 串,且 \(Z\)\(T\)可为空的 不等于 \(T\) 的前缀,且有 \(R_g > S[i..k-1]\)

\(j = k - \left|T\right|\),也就是上一个周期对应 \(k\) 的字符。

  1. \(S[k] = S[j]\),则 \(k \gets k + 1, j \gets j + 1\) 即可。
  2. \(S[k] > S[j]\),由引理 2 知 \(\overline{ZS[k]}\) 是一个 Lyndon 串,由于 Lyndon 分解要保证 \(R_i \ge R_{i + 1}\),所以 \(\overline{T^{\alpha}ZS[k]}\) 成为了一个新的 Lyndon 串。
  3. \(S[k] < S[j]\),则 \(S[k]\) 不能被包含到 \(T^{\alpha}\) 里,因为 \(S[k]\) 的出现会导致更小的后缀的存在。所以 \(T^{\alpha}\) 要被分离出去,算法从 \(Z\) 的开头重新开始。

代码实现

下面是求出一个串的 Lyndon 分解的代码实现。

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define LL long long

const int N = 5e6 + 5;

int n, ans;
char str[N];

int main() {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    for(int i = 1; i <= n; ) {
        int j = i, k = i + 1;
        while(k <= n && str[j] <= str[k]) {
            if(str[j] < str[k])
                j = i, ++k;
            else
                ++j, ++k;
        }
        while(i <= j) {
            ans ^= i + (k - j) - 1;
            i += k - j;
        }
    }
    printf("%d", ans);
    return 0;
}

时间复杂度

不难发现,\(i\) 是单调递增的,且每次 \(k\) 移动的距离 不会超过 \(i\) 移动的距离,因此时间复杂度是 \(O(n)\) 的。

Bonus

事实上,循环的总次数不超过 \(4n - 3\)

空间复杂度

不难发现空间复杂度是 额外 \(O(1)\) 的。

例题

还咕着在。

写在最后

太高深了,这辈子都用不到这么神必的内容。