Duval 线性 Lyndon 分解算法

相等、变大、变小，分别发生什么 ​

若 $s[k]=s[j]$，新字符符合已有周期，令 $k\leftarrow k+1,j\leftarrow j+1$。差 $j-k=p$ 不变，扫描段只是继续读一份 $t$。

若 $s[k]<s[j]$，新字符比周期期待值大。此时整个 $s[i:j+1]$ 成为新的 Lyndon 块；令 $k\leftarrow i$，再令 $j\leftarrow j+1$，新差 $j-k$ 正好等于这个块的总长度。

若 $s[k]>s[j]$，则停止扫描。右边这个更小的字符使继续重复失效，当前完整的 $t$ 副本已经可以输出。到达串尾 $j=n$ 时也停止：未读字符不存在，不应越界比较。

关键是第二种情形为何合法。把旧段写成 $t^{q}r$，下一个期待字符是 $t[|r|]$；换成更大的 $c$ 后得到 $x=t^{q}rc$。取 $x$ 的任意真后缀。若起点落在 $t$ 的块边界，它会比整串更早走到这个较大的 $c$，所以整串更小。若起点落在块内部，先比较 $t$ 与该内部位置的循环移位：Lyndon 性质保证首个差异偏向 $t$ 更小；若比较提前遇到末尾的 $c$，将期待字符增大也只会使后缀更大。因此 $x$ 小于全部非空真后缀，仍为 Lyndon 词。[2, Lemmas 3–4]

这条扩张规则不是普通周期串都具备的性质。它依赖基本块 $t$ 已经是 Lyndon 词，因而算法必须从单字符开始并在每一步保持不变量。

一次输出多少个块 ​

扫描停止时，$p=j-k$，已扫描长度 $L=j-i$。其中完整副本数为 $q=\lfloor L/p\rfloor$，剩余前缀长 $L-qp<p$。输出 $q$ 份长度 $p$ 的因子，把 $i$ 向前移动 $qp$；余下的短前缀留到下一轮重新处理。

代码不必显式计算 $q$。只要原起点不断加 $p$，直到超过 $k=j-p$，输出的恰好就是这些完整副本：

def duval_intervals(s):
    n = len(s)
    i = 0
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        p = j - k
        while i <= k:
            yield (i, i + p)
            i += p

输出的是区间，调用者需要字符时再访问输入。空串不进入外循环，自然输出空序列。相等字符必须走 k += 1 分支；若每次都把 $k$ 重置为 $i$，便会把 aaaa 错当成越来越长的块，而它的正确分解是四个单字符。

为什么输出不会被未来推翻 ​

停止时扫描段为 $t^{q}r$。若因为较小字符 $c$ 停止，未输出的剩余串以 $rc$ 开头，其中 $r$ 是 $t$ 的真前缀且 $c<t[|r|]$，所以整个剩余串严格小于 $t$。若因为到达串尾停止，剩余串只是 $r$，同样严格小于 $t$；$r$ 为空时则已经结束。

根据 CFL 存在性，剩余串拥有一份合法分解。它的第一个因子是剩余串的前缀，因此不大于剩余串，进而小于 $t$。将 $q$ 份 $t$ 放在这份分解前面，所有块都是 Lyndon 词，顺序也非增，得到原未处理串的一份合法 CFL 分解。

唯一性定理随即保证，这批 $t$ 正是正确的前几个因子。对剩余串重复同一论证，就证明整段算法正确。这样既解释了为何可以一次输出多个相同块，也解释了为什么短前缀必须留下：它已经属于下一份较小因子的开头。

完整手算十二个字符 ​

输入位置与字符为：

第一轮 $i=0$。位置一仍是 b，相等分支把 $(j,k)$ 从 $(1,0)$ 改成 $(2,1)$；位置二为 a<b，扫描停止。$p=2-1=1$，输出区间 $[0,1),[1,2)$，也就是两个 b。

第二轮从 $i=2$ 开始。比较轨迹如下，表内记录的是比较前的 $j,k$：

停止时 $j=12,k=8,p=4$。已扫描段 aabbaabbaa 是 $(\mathtt{\text{aabb}}{)}^2\mathtt{\text{aa}}$，所以只输出 $[2,6),[6,10)$，不能把最后的 aa 塞进四字符因子。

第三轮 $i=10$，两个 a 给出周期一，输出 $[10,11),[11,12)$。三轮合起来就是前一页已经独立核验的六个因子。

迁移练习与反例 ​

对 abbabbaba，第一轮在位置八的 a 处遇到下降，已扫描 abbabbab。它是 $(\mathtt{\text{abb}}{)}^2\mathtt{\text{ab}}$，输出两个 abb，剩余 aba 再分成 ab|a。最终为 abb|abb|ab|a。

这个实例与串尾停止不同：下降字符本身还没被消费，下轮必须把它保留下来。如果把下一轮起点设成 $j+1$，就会丢失数据；若设成 $j$，又会丢掉未输出的短前缀。真正的下一轮起点是旧 $i+M$，由输出长度决定。

算法擅长顺序分解，却不意味着输入每到一个字符就能立刻永久输出所有前面因子。例如 aaa 暂时分成三个 a，再接 b 后整串 aaab 成为一个 Lyndon 词。完整字符串的线性扫描，与必须立即承诺输出的在线接口，是两种不同要求。

线性时间要给重新扫描的部分记账 ​

“$j$ 只往右走”不足以证明全局线性，因为下一轮会重置 $j$，剩余的短前缀会被重新扫描。这里用摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。，正确计费单位是本轮真正输出的字符数。

固定一轮起点 $i_0$，停止时令 $L=j-i_0$、$p=j-k$，输出字符数为

由于 $L=M+r$、$0\le r<p$，且至少输出一个完整块所以 $p\le M$，有 $L<2M$。本轮的字符比较和索引操作为 $O(L+M)=O(M)$。不同轮输出的字符互不重叠、总计恰为 $n$，因此全部扫描，包括重新扫描的残段，总成本为 $O(n)$。

代码中相等或变大的一步可能调用两次关系比较，停止时可能再调用一次；同样的批次账本给出少于 $4n$ 次字符关系比较的粗界。这里不追求不同实现的最优常数，线性结论依赖字符访问和比较是常数成本。

生成器只保存常数个下标，辅助工作空间为 $O(1)$ 个机器字；若调用者收集全部 $m$ 个区间，还需 $O(m)$ words 输出空间。把所有因子字符复制出来，字符总量仍为 $n$；不能把调用者存下的输出也称为常数空间。