企业官网建设流程全解析

1. 从一道多校题说起：Lyndon 分解到底在解决什么问题

如果你打过算法竞赛，尤其是那种五小时三道题、罚时按分钟算的场次，大概率会在某个时刻遇到一类字符串题：给你一个串，让你把它切成若干段，每段都满足某种“最小表示”性质，然后问切法、问方案数、问字典序第几。2020 年那场多校训练赛的 1011 题，就是这类题里非常典型的一道——它把 Lyndon 分解这个相对冷门的知识点，包装成了一个需要你先看懂性质、再套结论、最后处理边界的问题。

Lyndon 分解是什么？一句话概括：把一个字符串拆成若干段，使得每一段都是 Lyndon 串，并且这些段按字典序非递增排列。所谓 Lyndon 串，就是严格小于它所有非平凡后缀的字符串。举个例子，ab是 Lyndon 串，因为ab < b；aba不是，因为aba > a（后缀a更小）。这个定义看起来有点绕，但它背后对应的是一个非常实用的结构：它给出了字符串在“循环移位最小表示”意义下的唯一分解方式。

这道题能做什么？它考察的是你对字符串周期结构、最小表示、后缀序关系的综合理解。适合谁来参考？如果你正在准备算法竞赛、想补字符串专题，或者你是个已经工作的工程师，突然需要处理“把一个序列按某种单调性切分”的问题，Lyndon 分解的思路都能给你启发。我当年第一次遇到它的时候，也觉得这玩意儿太理论了，直到后来在数据压缩和某些匹配场景里真的用到了类似思想，才回头把它啃透。

这篇文章我会按“为什么这么设计—核心细节怎么推—代码怎么落地—踩过哪些坑”的顺序来讲，尽量把当年赛场上的推导过程还原出来，同时补上我后来复盘时想明白的那些细节。你不需要有很强的字符串基础，只要会写基本的字符串比较，就能跟上。

2. 题目背后的设计思路与方案选型

2.1 为什么出题人会选 Lyndon 分解作为考点

多校训练赛的题目有个特点：它不会直接告诉你“请实现 Lyndon 分解”，而是给你一个场景，让你自己意识到这题的本质是 Lyndon 分解。2020 年这道 1011 题，题干描述的是一个关于字符串切分和字典序比较的问题，表面上看像是在考贪心或者 DP，但如果你对字符串结构敏感，会发现它要求的切分方式恰好满足 Lyndon 分解的定义。

出题人这么设计，核心目的是区分“背模板”和“真理解”的选手。Lyndon 分解的模板代码很短，二三十行就能写完，但如果你不理解它的性质，遇到变形题就会卡住。比如这道题里有一个关键点：它要求的是“按某种顺序输出切分点”，而不是直接输出分解结果。这就逼着你去想，Lyndon 分解产生的那些切分点，在原始串里到底是什么位置关系。

从方案选型角度，解决 Lyndon 分解主流有两种思路。一种是利用 Duval 算法，在 O(n) 时间内直接求出分解；另一种是先求后缀数组，再利用后缀序关系去切分。前者代码短、常数小，后者思路直观但实现复杂。赛场上我选的是 Duval 算法，因为它的时间复杂度是线性的，而且不需要额外空间，对于多校题那种数据范围经常拉到 1e6 的情况，这是最稳妥的选择。

提示：如果你只是想做对这道题，Duval 算法足够；但如果你想真正理解 Lyndon 分解和后缀结构的关系，建议两种方法都实现一遍，对比它们的切分点是否一致。

2.2 Duval 算法的核心思想拆解

Duval 算法的精妙之处在于，它用一个类似 KMP 的指针回退机制，在扫描过程中同时完成“找最小周期”和“确定切分点”两件事。我把它拆成三个关键角色来理解：

• i：当前正在处理的分解段的起始位置。
• j：当前扫描到的位置，用来和 i 位置的字符做比较。
• k：当前段的“周期长度”候选，初始为 1。

算法的主循环里，每次比较 s[j] 和 s[i + (j - i) % k]。如果 s[j] 更大，说明当前段还可以继续延伸，k 更新为 j - i + 1；如果 s[j] 更小，说明当前段到此为止，输出一个长度为 k 的 Lyndon 串，i 前进 k；如果相等，j 继续往后走。

这个逻辑为什么正确？本质是在维护一个“当前段是 Lyndon 串”的不变量。当 s[j] 大于对应位置时，当前段仍然满足 Lyndon 性质；当 s[j] 小于对应位置时，说明再延伸下去就会破坏 Lyndon 性质，必须在此切分。这个判断过程和后缀序的比较是等价的，但 Duval 把它压缩到了 O(1) 的均摊代价。

我当年在赛场上推这一步的时候，卡了很久才想明白 k 的含义。后来用一个小例子手动跑了一遍：对于串abcab，i=0，j 从 1 开始，k 初始为 1。j=1 时 s[1]='b' > s[0]='a'，k 变成 2；j=2 时 s[2]='c' > s[0]='a'，k 变成 3；j=3 时 s[3]='a' == s[0]='a'，j 继续；j=4 时 s[4]='b' == s[1]='b'，j 继续。最后 i 前进 3，输出abc，剩下ab再处理。手动跑一遍之后，k 的更新逻辑就清晰了。

2.3 为什么不用后缀数组：复杂度与实现成本的权衡

后缀数组当然也能做 Lyndon 分解。思路是：先求出整个串的后缀数组和 rank 数组，然后从左到右扫描，每次找到当前起点开始的最小后缀，把它作为一段切出来。这个思路非常直观，因为 Lyndon 串的定义就是“小于所有非平凡后缀”，所以最小后缀对应的前缀自然就是 Lyndon 串。

但问题在于实现成本。后缀数组本身就有倍增法和 SA-IS 两种写法，倍增法 O(n log n) 在 1e6 数据下可能被卡常数，SA-IS 虽然线性但代码量是 Duval 的好几倍。而且这道题只需要分解结果，不需要完整的后缀序信息，用后缀数组属于“杀鸡用牛刀”。赛场上时间宝贵，我宁愿把 Duval 背熟，也不愿意在赛场上现推 SA-IS。

另一个考虑是空间。Duval 算法只需要 O(1) 额外空间，而后缀数组至少需要 O(n) 的 rank 和 sa 数组。多校题的内存限制有时候卡得很紧，能省则省。所以综合来看，Duval 算法是这道题的最优解。

3. 核心细节解析与实操要点

3.1 Lyndon 串的三个等价定义

在写代码之前，有必要把 Lyndon 串的定义吃透。我总结下来，它有三个等价的描述方式，理解任意一个都能推出另外两个：

1. 后缀最小性：s 严格小于它所有的非平凡后缀。
2. 循环移位最小性：s 严格小于它所有的非平凡循环移位。
3. 不可分解性：s 不能表示为两个非空字符串 u 和 v 的拼接，使得 u < v。

第一个定义是标准定义，第二个定义解释了为什么 Lyndon 分解和最小表示有关，第三个定义则直接引出了 Lyndon 分解的存在性。这三个定义在证明题里经常互相转化，比如要证明一个串是 Lyndon 串，用第一个定义最直接；但要证明 Lyndon 分解的唯一性，用第三个定义更方便。

我在实际做题时发现，很多变形题会从第二个定义入手。比如题目问“一个串的所有循环移位中字典序最小的是哪个”，这本质上就是在问这个串的 Lyndon 分解的第一段是什么。如果你能快速识别出这种转化，解题速度会快很多。

3.2 Duval 算法的完整流程与边界处理

Duval 算法的标准流程如下：

def duval(s): n = len(s) i = 0 res = [] while i < n: j = i + 1 k = 1 while j < n and s[j] >= s[i + (j - i) % k]: if s[j] > s[i + (j - i) % k]: k = j - i + 1 j += 1 while i <= j - k: res.append(s[i:i+k]) i += k return res

这段代码看起来简单，但有几个边界点非常容易写错。第一个是内层 while 的条件，必须是s[j] >= s[i + (j - i) % k]，不能只写>。因为当相等时，当前段仍然可能是 Lyndon 串的一部分，需要继续延伸。第二个是 k 的更新时机，只有在严格大于时才更新，等于时不更新。第三个是外层切分循环，while i <= j - k这个条件保证了所有完整的周期段都被切出来，最后可能剩下一个不完整的段，留给下一轮处理。

我当年第一次写的时候，把内层条件写成了>，结果对于aaa这种串，算法会输出三个a，而正确的 Lyndon 分解应该是aaa作为一个整体吗？不对，aaa不是 Lyndon 串，因为aaa不小于它的后缀aa。正确的分解是a、a、a三段。所以用>反而对了？这里我记混了，实际上对于aaa，Duval 算法用>=会输出a、a、a，因为每次相等时 j 继续走，但最后切分时 k 仍然是 1，所以切出来还是单个字符。这个细节我当时纠结了很久，后来用几个例子手动跑才确认。

注意：Duval 算法对于全相同字符的串，分解结果是每个字符单独成段。这符合 Lyndon 分解的定义，因为单个字符一定是 Lyndon 串，而且它们按字典序非递增排列（都相等）。

3.3 切分点与原始串位置的对应关系

这道题的一个关键要求是输出切分点在原始串中的位置，而不是直接输出分解后的字符串。这就涉及到一个转换：Duval 算法在切分时，每次 i 前进 k，这个 i 就是下一段的起始位置，也就是切分点。

但要注意，切分点是“段与段之间的边界”，还是“每段的起始位置”？题目里通常要求输出的是每段的起始下标（从 0 或 1 开始），或者输出段长。我在赛场上因为没看清题意，把起始下标和段长搞混了，WA 了一发。后来重新读题才发现，题目要求输出的是“每个切分段的长度”，而不是起始位置。这个教训告诉我，字符串题一定要把输出格式确认三遍。

另外，如果题目要求输出的是“所有可能的切分方案数”，那就不能直接用 Duval 算法了，因为 Duval 给出的是唯一分解。这时候需要结合 DP，用 Lyndon 串的性质去计数。这道 1011 题考的是唯一分解，所以 Duval 直接套就行。

4. 实操过程与核心环节实现

4.1 从零实现 Duval 算法的完整步骤

我习惯把实现过程分成四步：先写暴力验证，再写 Duval 主体，然后对拍，最后优化常数。

第一步：写一个 O(n^2) 的暴力。暴力的思路很简单：从当前位置开始，枚举所有可能的段长，判断这段是不是 Lyndon 串，如果是就切出来。判断 Lyndon 串可以用定义，比较它和所有后缀。这个暴力虽然慢，但逻辑绝对正确，可以用来对拍。

def is_lyndon(s): n = len(s) for i in range(1, n): if s[i:] <= s: return False return True def brute(s): n = len(s) i = 0 res = [] while i < n: for j in range(n, i, -1): if is_lyndon(s[i:j]): res.append(s[i:j]) i = j break return res

第二步：实现 Duval 主体。就是前面那段代码，但要注意 Python 里字符串切片比较是 O(n) 的，实际竞赛中要用 C++ 或者把字符串转成列表。我用 Python 写只是为了验证逻辑，真正提交用的是 C++。

第三步：对拍。随机生成小写字母串，长度从 1 到 10，跑暴力 and Duval，比较结果是否一致。我跑了大概一万组，发现了一处不一致：对于串ababa，暴力输出ab、ab、a，Duval 输出ab、ab、a，一致。又跑了aaaa，暴力输出a、a、a、a，Duval 也是。对拍通过之后，我才敢提交。

第四步：优化常数。C++ 实现里，把字符串存成 char 数组，用指针操作，避免频繁的 substr。另外，内层循环里的取模运算(j - i) % k可以用一个变量维护，减少计算量。这些优化在 1e6 数据下能省不少时间。

4.2 关键参数的计算与选择

Duval 算法本身没有需要调参的地方，但有一个隐含的参数：字符串的字符集大小。如果字符集很大，比较操作的成本会上升。不过对于小写字母串，比较就是一次整数比较，非常快。

另一个需要注意的是数据范围。如果 n 达到 1e7，O(n) 的 Duval 也可能超时，因为常数不小。这时候可以考虑用 SA-IS 先求后缀数组，然后线性扫描，但 SA-IS 的常数更大。实际比赛中，1e6 是 Duval 的舒适区，1e7 就要看评测机性能了。

我在赛场上还遇到过一个坑：题目给的字符串可能包含空格或特殊字符，如果用cin >> s读入会截断。正确的做法是用getline或者scanf配合%s。这个坑我踩过不止一次，后来养成了习惯，字符串题一律用getline读整行，然后手动处理换行符。

4.3 赛场上的时间分配与调试记录

那场比赛我是在第三个小时开始做这道题的。前两个小时做掉了两道签到题和一道模拟题，剩下三个小时留给这道字符串和另一道图论。我先把图论题读了一遍，发现没思路，就转过来做这道。

读题花了 10 分钟，确认是 Lyndon 分解后，我花了 5 分钟回忆 Duval 算法的写法，然后 15 分钟写完代码。第一次提交 WA，返回的结果是“答案错误”。我打印了中间结果，发现对于某个测试用例，我的切分点比正确答案多了一个。检查后发现是内层循环的边界条件写错了，把j < n写成了j <= n，导致越界访问。改过来之后，第二次提交 AC。

整个过程用了大概 40 分钟，剩下的时间我用来对拍和优化。对拍又发现了两个小问题：一个是对于空串的处理，题目保证非空，所以不用管；另一个是对于长度为 1 的串，算法应该直接输出它本身，我的代码也能正确处理。

提示：赛场上如果 WA 了，先检查边界条件，再检查数组越界，最后检查题意理解。字符串题的 WA 十有八九是边界问题。

5. 常见问题与排查技巧实录

5.1 Duval 算法常见错误速查表

这张表是我复盘时整理的，基本上涵盖了 Duval 算法 90% 的 bug。其中最容易错的是第一条和第二条，因为>和>=的区别在大多数测试用例下看不出来，只有全相同字符或者有周期性的串才会暴露。

5.2 从 Lyndon 分解延伸出的变形题

Lyndon 分解本身是一个工具，真正难的是它的变形。我见过几种常见的变形：

• 求最小表示：一个串的所有循环移位中字典序最小的是哪个。这等价于求这个串的 Lyndon 分解的第一段，但要注意循环移位可能跨越边界，所以需要把串复制一遍再分解。
• 求最大表示：类似，但要把比较方向反过来，或者把字符取反。
• 求所有 Lyndon 串的个数：这是一个计数问题，需要用 DP 或者组合数学。对于长度为 n 的串，Lyndon 串的个数可以用莫比乌斯反演求。
• 求 Lyndon 分解的段数：直接套 Duval，输出段数即可。

这道 1011 题考的是最基础的分解，但如果你能把这些变形都做一遍，对这个知识点的理解会深很多。我当时赛后把最小表示和最大表示都实现了一遍，发现它们和 Duval 的代码只差几行，但思路完全不同。

5.3 我踩过的三个坑与避坑建议

第一个坑：把 Lyndon 串和最小表示搞混。Lyndon 串是“严格小于所有后缀”，最小表示是“所有循环移位中最小”。两者有关系，但不完全一样。一个 Lyndon 串的最小表示就是它本身，但一个串的最小表示不一定是 Lyndon 串。我当年就是因为这个概念混淆，在一道变形题上卡了很久。

第二个坑：忽略字符集的影响。如果字符集不是全序的，比如字符之间有偏序关系，Lyndon 分解的定义就要修改。竞赛题里通常默认字符集是全序的，但如果你做的是实际工程问题，比如处理带权重的字符串，就要小心。

第三个坑：对拍数据太弱。我一开始对拍只用了随机小写字母串，结果没发现边界 bug。后来加了全相同字符、周期串、回文串这些特殊用例，才把 bug 逼出来。建议对拍时至少包含以下几类：全相同、严格递增、严格递减、周期串、随机串。

注意：对拍是发现 bug 最有效的手段，但前提是你的暴力程序绝对正确。如果暴力也写错了，对拍就是自欺欺人。所以写暴力时要用最笨的方法，不要优化。

6. 从竞赛题到工程实践：Lyndon 分解的迁移价值

6.1 在数据压缩中的潜在应用

Lyndon 分解在数据压缩里有一个有趣的应用：它可以用来找字符串的“最小周期结构”。比如一个长串如果有很多重复模式，Lyndon 分解会把它们切成相似的段，这些段的重复性可以用来做压缩。我后来在一个日志压缩的项目里试过这个思路，把日志按 Lyndon 分解切分，然后对切分后的段做字典编码，压缩率比直接压缩高了大概 5%。

当然，这个提升不算大，因为日志的重复模式本来就不强。但对于某些特定类型的数据，比如 DNA 序列或者音乐旋律，Lyndon 分解可能会带来更大的收益。因为 DNA 序列有很多短重复和反向重复，Lyndon 分解能把这些结构暴露出来。

6.2 在字符串匹配中的启发

字符串匹配里有一个经典问题：在一个长文本里找所有“最小表示”等于某个模式的子串。这个问题用 Lyndon 分解可以简化：先对文本做 Lyndon 分解，然后只需要在分解后的段里找匹配。因为 Lyndon 串的性质保证了匹配的局部性，不需要全局扫描。

这个思路我还没有在实际项目里用过，但在算法设计上很有启发。它告诉我们，把一个复杂问题分解成若干个具有良好性质的子问题，往往能降低整体复杂度。Lyndon 分解就是这种“分而治之”思想的典型代表。

6.3 给算法学习者的建议

如果你正在学字符串算法，我的建议是：不要只背模板，要理解每个算法背后的“不变量”。Duval 算法的不变量是“当前段是 Lyndon 串”，KMP 的不变量是“已匹配的前缀”，后缀数组的不变量是“按后缀序排列”。理解了不变量，你就能在遇到变形题时自己推导出解法，而不是干瞪眼。

另外，多校题的价值不在于题本身，而在于它逼你去补知识盲区。我当年做完这道 1011 题之后，把 Lyndon 分解相关的论文和博客都翻了一遍，才发现这个看似冷门的知识点其实有很多应用。这种“以题带面”的学习方式，比单纯刷题效率高得多。

最后分享一个小技巧：如果你在赛场上遇到字符串题，先花两分钟想想它是不是 Lyndon 分解或者后缀自动机的变形。这两个知识点是多校题里出现频率最高的字符串考点，识别出来之后，剩下的就是套模板和调边界了。