字符串，太深刻了。

Lyndon 理论，太神奇了。

---

本文详细介绍了 Lyndon 理论的相关内容，并且几乎所有定理和推论都给出了相关证明，同时部分算法给了几道配套例题。

希望读者阅读后能对 Lyndon 理论有深刻的理解。

全篇太长了，故分开来发。

0. 初步的定义 & 约定

• 长度：记为 $|s|$。

• 字符：用 $s[i]$ 表示串 $s$ 的第 $i$ 个字符。$s$ 中的字符标号为 $1,2,\ldots,n$。单个字符也被视作字符串。

• 字符集：记为 $\Sigma_s$。

• 字符串的比较：若 $s$ 的字典序比 $t$ 小，记为 $s<t$。类似地有 $\leq,>,\geq$。

• 子串：$s[l\dots r]$ 表示将 $s[l],s[l+1],\ldots,s[r]$ 顺次连接而成的字符串。

• 前缀 & 后缀：前缀为字符串开头的子串，即 $s[1\dots i]$；后缀为字符串结尾的子串，即 $s[i\dots n]$

  记 $\mathrm{pre}(s)$ 为 $s$ 的前缀集合，$\mathrm{suf}(s)$ 为 $s$ 的后缀集合。

• 真前缀 & 真后缀：称一个前缀/后缀为真前缀/真后缀，当且仅当它与原串 $s$ 不相等。

• 字符串的拼接：记 $st$，$s \cdot t$ 为字符串 $s$，$t$ 顺次连接而得的串。

• 字符串的幂：定义 $s^k = \overbrace{ss\ldots s}^{\text{共 } k \text{ 个}}$，即 $k$ 个 $s$ 顺次连接而得的串。

1. Lyndon 串（Lyndon Word）

1.1 定义

• Lyndon 串（Lyndon Word）：对于字符串 $s$，如果 $s$ 的字典序严格小于 $s$ 的所有后缀的字典序，我们称 $s$ 是 Lyndon 串。换句话说，对于一个字符串，若其本身就是其最小后缀，则称它为 Lyndon 串。
• Lyndon 前缀（Lyndon Prefix）：如果字符串 $s$ 的一个前缀 $s[1 \dots i]$ 是一个 Lyndon 串，那么它就是一个 Lyndon 前缀。
• Lyndon 后缀（Lyndon Suffix）：如果字符串 $s$ 的一个后缀 $s[i \dots n]$ 是一个 Lyndon 串，那么它就是一个 Lyndon 后缀。

1.2 性质

• 引理 1.2.1：若字符串 $a$ 和 $b$ 互不为对方的前缀，则对于任意 $c_1, c_2$，$ac_1 < bc_2 \Leftrightarrow a < b$。

充分性：因为 $a$ 不是 $b$ 的真前缀，那么比较完前 $min{|a|,|b|}$ 位就可以确定 $a<b$。

必要性：显然。

• 引理 1.2.2：若字符串 $a$ 和 $b$ 长度相同，则对于任意 $c_1, c_2$，$ac_1 < bc_2 \implies a \le b$。

如果 $a>b$，显然 $ac_1 > bc_2$，矛盾。

故 $a \le b$。

• 定理 1.2.1：Lyndon 串的字典序严格小于其所有的非空真后缀。

根据定义可得。

• 定理 1.2.2：对于任意一个长度大于 1 的 Lyndon 串 $s$，其不存在 Border（即不存在既是真前缀又是真后缀的子串）。

如果 $s$ 有一个 Border $t$，那么 $t$ 是 $s$ 的真后缀，根据定义 $s < t$。但 $t$ 也是 $s$ 的前缀，前缀的字典序不可能大于原串，产生矛盾。

• 定理 1.2.3：对于任意一个 Lyndon 串 $s=ab$，有 $a<b$（$a,b$ 均非空）。

由定义有 $ab<b$，且显然有 $a<ab$，所以 $a<b$。

• 推论 1.2.3.1：对于任意一个 Lyndon 串 $s$，其真前缀和真后缀分别为 $a$ 和 $b$，有 $a<b$（$a,b$ 均非空）。

由定义有 $s<b$，且显然有 $a<s$，所以 $a<b$。

• 推论 1.2.3.2：对于任意一个 Lyndon 串 $s$ 的前缀 $t$（可以有 $t$ 和 $s$ 相等），其真后缀的字典序始终大于或等于与其长度相同的真前缀。形式化地讲，$\forall i\in[2, |t|]$，都满足：
  $$t[i \dots |t|] \ge t[1 \dots |t|-i+1]$$

令 $s=tv$。

根据定义，有：$$t[i \dots |t|]v > tv$$

我们考虑前 $|t|-i+1$ 个字符，分别是 $t[i \dots |t|]$ 和 $t[1 \dots |t|-i+1]$。

根据引理 1.2.2，有：$$t[i \dots |t|]\ge t[1 \dots |t|-i+1]$$

证毕。

• 定理 1.2.4：对于任意一个串 $a$ 和任意一个 Lyndon 串 $b$ ，有 $a<b \Leftrightarrow ab<b$

情况一：若 $a$ 不是 $b$ 的真前缀

充分性：显然成立。

必要性：若 $|a|\geq |b|$，显然有 $a<b$；若 $|a|<|b|$，$b$ 不可能是 $a$ 的真前缀，根据引理 1.2.1，可得 $a<b$。

情况二：若 $a$ 是 $b$ 的真前缀

充分性：令 $b=at$，即证 $b<t$，其中 $t$ 为 $b$ 的后缀。根据 Lyndon 串的定义，显然有 $b<t$。

必要性：显然有 $a<b$ ，必要性成立。

• 定理 1.2.5：$s$ 是 Lyndon 串当且仅当 $s=ab$，$a<b$ 且 $a,b$ 均为 Lyndon 串（$a,b$ 均非空，$|s|\geq2$）。

充分性：$a < b$ 且 $a, b$ 均为 Lyndon 串 $\Rightarrow$ $ab$ 是 Lyndon 串。

我们要证明 $ab$ 是 Lyndon 串，即证明其严格小于它的所有非空真后缀。

$ab$ 的真后缀可以分为 $suf(a)b, b, suf(b)$ 。

由定义有 $a < suf(a)$，显然有：

$$ab < suf(a)b$$

由定理 1.2.4 有 $ab < b$，又 $b < suf(b)$，故：

$$ab < b < suf(b)$$

综上，$ab$ 严格小于其所有真后缀，故 $ab$ 是 Lyndon 串，证毕。

必要性：$s$ 是 Lyndon 串 $\Rightarrow$ 存在 $i$ 使得 $s[1\dots i-1]<s[i\dots n]$ 且 $s[1\dots i-1],s[i\dots n]$ 均为 Lyndon 串。

令 $b$ 为 $s$ 的最小真后缀，$s=ab$。（这里的 $a,b$ 即是命题中的 $s[1\dots i-1],s[i\dots n]$）

由定理 1.2.3，有 $a<b$。

因为不存在比 $b$ 更小的真后缀，故 $b$ 为 Lyndon 串。

考虑后缀 $suf(a)b$，有 $suf(a)b>b$，又根据定义有 $b>s=ab$，则 $$suf(a)b>ab$$

若 $suf(a)$ 不是 $a$ 的真前缀，因为 $a$ 不可能是 $suf(a)$ 的真前缀，由引理 1.2.1，可得 $suf(a)>a$，故 $a$ 为 Lyndon 串。

若 $suf(a)$ 是 $a$ 的真前缀，即 $pre(a)=suf(a)$，带入上式得 $pre(a)b>ab$，把相同的前缀拿掉后，有 $b>suf'(a)b$（注意这里 $suf'(b)$ 不一定和 $suf(a)$ 相等），与 $b$ 是 $s$ 的最小真后缀矛盾，故 $suf(a)$ 不能是 $a$ 的真前缀。

综上，$a$ 为 Lyndon 串，证毕。

• 定理 1.2.6：若字符串 $v$ 和字符 $c$ 满足 $vc$ 是某个 Lyndon 串 $s$ 的前缀，则对于字符 $d > c$ 有 $vd$ 是 Lyndon 串。

设 $s=vct$，由定义得 $v[i\dots |v|]ct>vct$。

我们要证明 $vd$ 是 Lyndon 串，即证明其严格小于它的所有非空真后缀。真后缀分为两种情况：

情况一：长度大于 1 的真后缀，形如 $v[i\dots |v|] d \quad (i \in [2, |v|])$。

比较两边前 $|v|-i+2$ 个字符（即只比到 $c$ 的位置），由引理 1.2.2，必然有：

$$v[i\dots |v|] c \ge v[1 \dots |v|-i+2]$$

又 $d > c$，有：

$$v[i\dots |v|] d > v[1 \dots |v|-i+2]$$

因此，在字典序比较中，$v[i\dots |v|] d$ 在前缀阶段就已经严格大于 $vd$ 的前缀，则有：

$$v[i\dots |v|] d>vd$$

情况二：长度为 1 的真后缀，即 $d$。

因为 $s$ 是 Lyndon 串，显然其首字符 $v[1]$ 必然是 $s$ 中字典序最小的字符（或之一），故必有：

$$c \ge v[1]$$

结合已知条件 $d > c$，可得：

$$d > v[1]$$

故：

$$d>vd$$

综上，$vd$ 严格小于其所有真后缀，故 $vd$ 是 Lyndon 串。证毕。

2. Lyndon 分解（CFL 分解）

2.1 定义

• Lyndon 分解：字符串 $s$ 的 Lyndon 分解记为 $s=w_1w_2\dots w_k$，其中所有 $w_i$ 为 Lyndon 串，并且他们的字典序按照非严格递减排序，即 $w_1\geq w_2\geq\dots\geq w_k$。可以发现，这样的分解存在且唯一。

2.2 性质

在 Lyndon 分解 $s = w_1 w_2 \dots w_k$ 中

• 定理 2.3.1：任何字符串的 Lyndon 分解都是唯一的。

假设存在两种分解方式，证明矛盾即可。

这里就偷懒不证了。

• 定理 2.3.2：如果截取分解中的连续一段 $wi w{i+1} \dots w_j$（其中 $1 \le i \le j \le k$），这段子串的 Lyndon 分解恰好就是 $wi, w{i+1}, \dots, w_j$ 本身。

显然 $wi, w{i+1}, \dots, w_j$ 符合 Lyndon 分解的定义，并且由于 Lyndon 分解的唯一性，故 $wi w{i+1} \dots w_j$ 的 Lyndon 分解恰好就是 $wi, w{i+1}, \dots, w_j$ 本身

• 定理 2.3.3：Lyndon 分解中的最后一个 Lyndon 因子 $w_k$ 必然是整个字符串 $s$ 的字典序严格最小的后缀。

我们要证明对于 $s$ 的任意非空后缀 $t$，都有 $w_k \le t$。

$s$ 的后缀可以分为两类：

情况一： $t$ 是 $w_k$ 的一个非空后缀。

根据定义，$w_k \le t$ 显然成立。

情况二：$t$ 跨越了多个因子

设后缀 $t = wi' w{i+1} \dots w_k$，其中 $w_i'$ 是 $w_i$ 的某个后缀（可以是 $w_i$ 本身），且 $i < k$。

假设此时恰有 $w_i'=w_i$。

如果 $w_i > w_k$，故 $t=wi w{i+1} \dots w_k > w_k$。

如果 $w_i = w_k$，由于 $w_1\geq w_2\geq\dots\geq w_k$，显然中间所有的因子也必须相等，即 $wm = w{m+1} = \dots = w_k$。此时 $t = w_k^r$（其中 $r$ 是因子的个数），显然 $t=w_k^r > w_k$。

即使 $w_i'$ 是 $w_i$ 的真后缀，根据 Lyndon 串定义 $w_i' > w_i$，同样可以推导出 $t=wi' w{i+1} \dots w_k > w_k$。

• 定理 2.3.4：Lyndon 分解中的第一个 Lyndon 因子 $w_1$ 是 $s$ 的最长 Lyndon 前缀；最后一个因子 $w_k$ 是 $s$ 的最长 Lyndon 后缀。

我们要证明：对于任何长度大于 $|w_1|$ 的前缀 $p = s[1 \dots j]$（即 $j > |w_1|$），$p$ 一定不是 Lyndon 串。

设 $p$ 跨越了前 $r$ 个 Lyndon 因子（$r \ge 2$），即 $p = w_1 w2 \dots w{r-1} w_r'$，其中 $w_r'$ 是 $w_r$ 的一个非空前缀（可以是 $w_r$ 本身）。

根据 Lyndon 分解的性质，$w_1 \ge w_2$，我们可以分类讨论。

情况一：$w_1 > w_2$

往后面加一些东西显然不改变不等号方向，于是有 $w_1 w_2 \dots > w_2 \dots$。

由于 $p$ 拥有一个真后缀 $suf(p) = w_2 \dots w_r'$，显然 $p > suf(p)$。

根据 Lyndon 串的定义，$p$ 不是 Lyndon 串。

情况二：$w_1 = w_2$

有 $p = w_1 w2 \dots w{r-1} w_r' = w_1 w1 \dots w{r-1} w_r'$。

那么 $p$ 的一个真后缀就是 $suf(p)=w_2 \dots w_r'=w_1 \dots w_r'$。

不难发现前缀都有 $w_1$，此时只需比较 $w_1w3 \dots w{r-1} w_r'$ 和 $w_3 \dots w_r'$。

若 $w_1 > w_3$，显然有 $p > suf(p)$，$p$ 不是 Lyndon 串。

若 $w_1 = w_3$，重复上述步骤，后面以此类推。

如果一直相等，最后会剩下 $w_1 w_r'$ 和 $w_r'$，由于 $w_1\ge w_r \ge w_r'$，那么 $w_1 w_r'>w_r'$，于是有 $p > suf(p)$，$p$ 不是 Lyndon 串。

综上，始终有 $p > suf(p)$，故 $p$ 不是 Lyndon 串，证毕。

后缀的证明和前缀类似，节省空间，这里就不证了。

• 定理 2.3.5：后缀 $s[i \dots n]$ 的第一个 Lyndon 因子的末尾，恰好在“第一个字典序严格小于 $s[i \dots n]$ 的后缀”出现的位置之前。

令 $t=s[i \dots n]$。

设 $t$ 的唯一 Lyndon 分解为 $t = w_1 w_2 \dots w_k$，且 $w_1 \ge w_2 \ge \dots \ge w_k$。

我们首先证明：对于所有起始于 $w_1$ 内部的位置 $j$（即 $1 < j \le |w_1|$），以它开头的后缀 $t[j\dots n]$ 一定严格大于 $t$，即 $t[j\dots n]>t$。

显然 $t[j\dots n] = w_1[j \dots |w_1|] w_2 \dots w_k$。

我们要将它与原串 $t = w_1 w_2 \dots w_k$ 进行比较。

根据 Lyndon 串的定义，$w_1$ 严格小于它的所有真后缀。因此：

$$w_1 < w_1[j \dots |w_1|]$$

根据定理 1.2.2，$w_1[j \dots |w_1|]$ 不是 $w_1$ 的前缀，又因为 $w_1$ 显然不可能是 $w_1[j \dots |w_1|]$ 的前缀，根据引理 1.2.1，有：

$$w_1 w_2 \dots w_k < w_1[j \dots |w_1|] w_2 \dots w_k$$

即 $t<t[j\dots n]$。

接下来我们需要证明：以 $|w_1| + 1$ 开头的后缀，一定严格小于 $t$，即 $t[|w_1| + 1\dots n]<t$。

显然 $t[|w_1| + 1\dots n] = w_2 w_3 \dots w_k$。

我们只需证明 $w_2 w_3 \dots w_k<w_1 w_2 \dots w_k$。

考虑到 $w_1 \ge w_2 \ge \dots \ge w_k$，假设前 $r$ 个 Lyndon 因子完全相等，即 $w_1 = w_2 = \dots = wr > w{r+1}$（若 $r = k$，则 $w_{r+1}$ 视为空串）。

此时我们只需证 $w1^{r-1} w{r+1} \dots w_k<w1^r w{r+1} \dots w_k$。

它们拥有公共前缀 $w_1^{r-1}$。将其消去后，问题转化为比较以下两个字符串：

$$A = w{r+1} w{r+2} \dots w_k,B = w1 w{r+1} \dots w_k$$

如果 $A$ 是空串，那么 $A < B$ 显然成立。

如果 $A$ 不是空串，我们已知 $w1 > w{r+1}$，此时需要分两种情况：

情况一：$w_{r+1}$ 不是 $w_1$ 的真前缀

这种情况下由于 $w1 > w{r+1}$ 且不包含前缀关系，由引理 1.2.1，显然有 $A < B$。

情况二：$w_{r+1}$ 是 $w_1$ 的真前缀

设 $w1 = w{r+1} u$（$u$ 不能为空）。

此时

$$A = w{r+1} w{r+2} \dots wk,B = w{r+1} u w_{r+1} \dots w_k$$

因为 $w_1$ 是 Lyndon 串，根据定义有 $u > w_1$。

于是有 $u > w1 \ge w{r+1} \ge w{r+2}$，即 $u > w{r+2}$。

现在，我们在 $A$ 和 $B$ 中同时消去公共前缀 $w_{r+1}$，剩下：

$$A' = w_{r+2} \dots wk,B' = u w{r+1} \dots w_k$$

此时 $A'$ 以 $w{r+2}$ 开头，$B'$ 以 $u$ 开头，且已知 $u > w{r+2}$。你会发现，这与我们刚才面临的局面完全一致。

我们可以不断重复上述过程。由于每次 $B$ 剩余部分开头的字符串，必然是上一轮 $u$ 的真后缀，因此它也就是 $w_1$ 的某个真后缀。根据 Lyndon 性质，它永远严格大于 $w_1$，自然也严格大于下一个将要比较的 Lyndon 因子 $w_j$。

最终要么遇到了情况一结束，要么重复情况二直到 $A$ 的因子被消耗殆尽变成空串，而此时 $B$ 还有剩余，于是一定有 $A < B$。

证毕。

• 推论 2.3.5.1：对于任意字符串的 Lyndon 分解，总有 $w_1\dots w_k>w_2 \dots wk>\dots>w{k-1} w_k> w_k$。

2.3 算法

2.3.1 Duval 算法

Duval 可以在 $\mathcal{O}(n)$ 的时间内求出一个串的 Lyndon 分解。

该算法需要维护三个变量 $i,j,k$，这三个指针将整个字符串分成了四个部分 $s[1,i-1],s[i,k-1],s[j,k-1],s[k,n]$ :

• $s[1,i-1]$：这部分的 Lyndon 分解已经完成。
• $s[i,k-1]$：这部分可以被表示成 $t^h+v$，其中 $t$ 是一个 Lyndon 串，$t^h$ 表示 $t$ 循环 $h$ 次，$v$是 $t$ 的一个可空真前缀。
• $s[j,k-1]$：注意这部分是包含在上一个部分中的，其中$j=k–|t|$。
• $s[k,n]$：这部分还未处理，此时正在考虑 $k$。

考虑k有三种情况:

• $s_j=s_k$：可以将 $t$ 继续循环下去，因此 $j$ 往后移一位，考虑下一个 $k$。
• $s_j<s_k$：可以将 $t^c+v+s_k$ 合并为一个 Lyndon 串，因此 $j$ 设为 $i$，考虑下一个 $k$。
• $s_j>s_k$：可以将 $t$ 单独作为 Lyndon 分解中的一个串，然后从 $v$ 的开头开始重新考虑，因此 $i$ 设为 $v$ 的开头，$j,k$ 分别设为 $i,i+1$。

string s;
cin>>s;
int n=s.length();
s=' '+s;
for(int i=1;i<=n;){
    int j=i,k=i+1;
    while(k<=n and s[j]<=s[k]){
        if(s[j]<s[k])j=i;
        else j++;
        k++;
    }
    while(i<=j){
        cout<<i+k-j-1<<' ';  //分解后每个 Lyndon 串的右端点
        i+=k-j;
    }
}

2.3.2 SA + 单调栈算法

注意：这个算法远不及 Duval 算法高效，平时最常用还是 Duval 算法，写在这里仅为了拓宽思路。（事实上，某些题甚至可以用 Lyndon 分解吊打 SA，同时也存在用 Lyndon 理论求 SA 的算法）

我们求出后缀数组（SA）和 $rank$ 数组后。

根据定理 2.3.5，这个问题转化为：在 $rank$ 数组中，寻找 $i$ 后面第一个 $j$ 使得 $rank[j] < rank[i]$。

我们用单调栈对 $rank$ 数组预处理一下，就能 $O(1)$ 找到 $j$ 了。

复杂度：$O(n)$ 或 $O(n \log n)$ 取决于 SA 的实现。

2.4 应用

• 求每个前缀的最小前缀/后缀。

• 求字符串的最小表示法。

• 等等。

2.5 例题

HDU6761 Minimum Index

题意：求每个前缀的最小后缀的起始位置下标。

题解：

根据定理 2.3.1，对于每个前缀我们取最后一个 Lyndon 因子就是答案。Duval 过程中边找边记录答案即可。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define int ll
const int maxn = 20000005, mod = 1000000007, INF = 1e9;
int ans[maxn];

void solve() {
    string s;
    cin>>s;
    int n=s.length();
    s=' '+s;
    ans[1]=1;
    for(int i=1;i<=n;){
        int j=i,k=i+1;
        while(k<=n and s[j]<=s[k]){
            if(s[j]<s[k])ans[k]=j=i;
            else ans[k]=ans[j]+k-j,j++;
            k++;
        }
        while(i<=j){
            i+=k-j;
        }
        ans[k]=i;
    }
    int sum=0;
    for(int i=1,x=1;i<=n;i++,x=x*1112LL%mod){
        sum+=ans[i]*x%mod;
        sum%=mod;
    }
    cout<<sum<<'\n';
}

signed main() {
    ios::sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

P13270 【模板】最小表示法

题意：给定一个长度为 $n$ 的字符串 $s$，求与 $s$ 循环同构的字典序最小的串（即字符串 $s$ 的最小表示）。

题解：

设 $t = ss$，则需要找出 $t$ 的长度为 $n$ 的最小子串。

对 $t$ 做 Lyndon 分解，然后寻找这个分解中的一个 Lyndon 串 $w_i$，使得它的起点小于 $n$ 且终点大于等于 $n$。

可以很容易地使用 Lyndon 分解的性质证明，子串 $w_i$ 的首字符就是 $s$ 的最小表示法的首字符，即我们沿着 $w_i$ 的开头往后 $n$ 个字符组成的串就是 $s$ 的最小表示法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000050, mod = 1e9 + 7, INF = 1e9;

int main() {
    ios::sync_with_stdio(0);
    int n;
    cin>>n; 
    string s;
    cin>>s;
    s=' '+s+s;
    int ans=0;
    for(int i=1;i<=2*n;){
        int j=i,k=i+1;
        while(k<=2*n and s[j]<=s[k]){
            if(s[j]<s[k])j=i;
            else j++;
            k++;
        }
        while(i<=j){
            if(i+k-j-1<n) ans=max(ans,i+k-j-1)+1;
            i+=k-j;
        }
    }
    cout<<s.substr(ans,n)<<'\n';

    return 0;
}

P14190 [ICPC 2024 Hangzhou R] Dividing Sequence

题意：给定一个长度为 $n$ 的字符串 $s$，将其拆成两个子序列 $a$ 和 $b$，使得字典序 $a<b$ 且最小化 $b$ 的字典序。

题解：

考虑对原串 $s$ 做 Lyndon 分解 $s = w_1 w_2 \dots w_k$，且 $w_1\geq w_2\geq\dots\geq w_k$。

$i$ 从 1 开始，

若 $w{2i-1}=w{2i}$，则将这两个串分别接在 $a,b$ 的末尾，$i++$。

若 $w{2i-1}\neq w{2i}$，将 $w_{2i-1}$ 接到 $b$ 之后，剩下的所有串按顺序接到 $a$ 的末尾，此时的$b$就是答案。

详细证明可以见题解区，这里就不证了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000050, mod = 1e9 + 7, INF = 1e9;

void solve() {
    int n;
    cin>>n;
    vector<int> s(n+1);
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    vector<int> ans;
    for(int i=1;i<=n;){
        int j=i,k=i+1;
        while(k<=n and s[j]<=s[k]){
            if(s[j]<s[k])j=i;
            else j++;
            k++;
        }
        int f=0;
        int len=k-j;
        while(i<=j){
            f^=1;
            if(f){
                for(int t=i;t<=i+len-1;t++){
                    ans.push_back(s[t]);
                }
            }
            i+=len;
        }
        if(f) break;
    }
    cout<<ans.size()<<'\n';

    for(int x:ans){
        cout<<x<<' ';
    }
    cout<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

参考资料 ：

• Lyndon & Runs - command_block
• Lyndon 分解 - OI Wiki
• Lyndon 理论学习笔记 - Sk_sync_closer
• The Runs Theorem 和 Lyndon Tree 学习笔记 - Neal_lee