Chen–Fox–Lyndon 唯一分解

从单字符开始，为什么总能得到一份 ​

每个字符都是 Lyndon 词，因此先按单字符分割，已经满足“每块合法”。若相邻两块 $u<v$，上一页的连接引理保证 $uv$ 仍是 Lyndon 词。把这两块合并，因子数量减少一。

只要还存在递增相邻对就继续合并。块数不能无限下降，所以过程终止；终止时不存在 $u<v$ 的相邻对，即所有因子非增。连接顺序始终没变，得到的仍是原词。存在性因此得到证明。

这个论证还没有证明切法唯一，也没有保证任意合并实现都在线性时间完成。它只保证至少有一份合法结果。把“某个构造会终止”和“只有一个结果”分开，能避免在设计算法时偷用尚未证明的结论。

最后一块藏在全部后缀里 ​

在任意合法分解 $w={\ell }_1\cdots {\ell }_m$ 中，${\ell }_m$ 是 $w$ 的字典序最小非空后缀。

取一个非空后缀 $z$。如果它恰从某个因子 ${\ell }_j$ 的边界开始，则 $z$ 以 ${\ell }_j$ 为前缀，而 ${\ell }_m\le {\ell }_j$；在较大的词后继续接字符不会把它降到较小者之前，所以 ${\ell }_m\le z$。

如果 $z$ 从 ${\ell }_j$ 内部开始，写成 $z=t{\ell }_{j+1}\cdots {\ell }_m$，其中 $t$ 是 ${\ell }_j$ 的非空真后缀。Lyndon 后缀判据给出 ${\ell }_j<t$，再结合非增顺序，有

所以这种后缀严格更大。所有后缀都已覆盖，${\ell }_m$ 确实最小。不同起点的有限后缀长度不同，内容不可能完全相等，因此这个最小非空后缀唯一。

例如 banana 的非空后缀是 banana,anana,nana,ana,na,a，最小的是最后的 a，因而任何合法分解都必须以这一块结束。移去它，对 banan 重复论证，最小后缀是 an；继续得到 ban 的 an，最后剩 b。

现在唯一性也清楚了：两份合法分解的末因子都必须是同一个最小后缀；删除它们后，剩余前缀仍有两份合法分解。按字符串长度归纳，所有前面的因子也逐一相同。无需猜测哪种合并顺序更“标准”，定理会强迫所有正确合并过程会合。

怎样检查别人交来的切分 ​

给一组边界，先核验它们恰好覆盖输入且没有空块，再逐块检查 Lyndon 条件，最后检查相邻因子非增。三项全部通过，就可以凭唯一性确定这是正确 CFL 分解；检查器不必重演构造过程。

例如声称 abab 分成 ab|ab，三个条件都满足。声称分成整块 abab，覆盖虽正确，Lyndon 条件却失败；声称分成 a|b|a|b，每块都合法，但出现 $a<b$ 的递增对，也失败。

用逐后缀比较核验每块，若块长为 $n_1,\dots ,n_m$，可给出 $O(\sum n_i^2+n)$ 的朴素检查上界，最坏为 $O(n^2)$。证书只要 $m-1$ 个内部切点，长度 $O(m\log (n+1))$ bits；证书短并不自动意味着任何检查实现都快。

CFL 不是“尽量使用最短块”，也不是“按字典序递增”。例如整串 aab 已是 Lyndon 词，它的唯一分解只有一块；分成 a|ab 虽每块合法，却递增。这个反例同时检验了顺序方向和唯一性条件。

单元中的一次完整核验 ​

对 bbaabbaabbaa，分解为

切点是 $0,1,2,6,10,11,12$。aabb 已在上一页通过后缀判据，单字符自动合法，且 $\mathtt{\text{b}}>\mathtt{\text{aabb}}>\mathtt{\text{a}}$，因此这张证书足够确定整份分解。

注意它的本原根是 bbaa，却没有任何 CFL 因子等于 bbaa。本原根要求整串由同一块重复，CFL 要求每个块是严格最小旋转且因子非增；两种分解回答不同的问题。下一页将对同一十二字符实例真正运行线性算法，把这份证书从“可验证”变成“可高效生成”。

一个容易理解、却还不够快的构造 ​

存在性证明可以实现成栈。从左到右读字符，先把单字符作为新因子压入；如果栈顶两块递增，就合并，直到恢复非增顺序。

def cfl_by_merging(s):
    factors = []
    for ch in s:
        factors.append(ch)
        while len(factors) >= 2 and factors[-2] < factors[-1]:
            right = factors.pop()
            left = factors.pop()
            factors.append(left + right)
    return factors

读完每个前缀时，不变量有三条：栈里的块连接成这个前缀；每块都是 Lyndon 词；因子从底到顶非增。压入新字符只可能破坏最顶上的顺序，合并后也只需继续检查新相邻对，所以循环恢复全部不变量。

处理 banana 时，读到前两个字符得到 b|a；读到 n，合并 a|n 为 an；再读 a,n，同样形成第二个 an，但两个相等块不合并；最后的 a 保持在末尾。输出正是四块。

每次成功合并减少一个块，因此总合并次数至多 $n-1$。但这不能推出字符时间线性：比较两块可能扫描长公共前缀，连接也可能复制全部字符。上面朴素实现有 $O(n)$ 次块操作、每次最坏 $O(n)$ 字符工作，故可保证 $O(n^2)$ 时间，峰值存储为 $O(n)$ 个字符外加因子表。Duval 算法理路Duval 线性 Lyndon 分解算法Duval's algorithm · Duval factorization · Duval算法用三个索引维护 Lyndon 块的重复前缀，遇到较小字符或串尾就批量输出完整块，在 O(n) 时间和常数工作空间内生成 CFL 分解。将用索引和重复段不变量避免这些反复复制与比较。