Lyndon分解

What · 是什么

Lyndon 串（简单串）：s 严格小于它的所有非平凡后缀（等价地严格小于所有非平凡循环同移）。例：a,b,ab,aab,abb,ababb,abcd 是 Lyndon 串。Lyndon 分解：s=w1w2…wk，每个 wi 是 Lyndon 串且 w1≥w2≥…≥wk（非严格递减），存在且唯一。Duval 算法在 O(n) 时间、O(1) 附加空间求出分解：维护三个指针 i（s2 起点）、j（s3 起点）、k（s2 中当前比较位），把当前串分为已定分解 s1、近似 Lyndon 串 s2（形如 ww…w·前缀）、未处理 s3。比较 s[j] 与 s[k]：相等则 j,k 各 +1；s[j]>s[k] 则 s2+s[j] 成为新的 Lyndon 串（j+1,k 回到 i）；s[j]<s[k] 则 s2 不再近似简单，截出长度 j−k 的循环节（Lyndon 串）加入分解，i 前进。推论应用：最小循环移位（对 ss 做 Duval，找跨越中点且起点<n 的 Lyndon 块起点）。

Why · 为什么

How · 实现

伪代码

# Duval 算法
factorization = []
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      # 成为新的 Lyndon 串
        else: k += 1
        j += 1
    while i <= k:
        factorization.append(s[i : i + j - k])
        i += j - k
return factorization

# 最小循环移位
s = s + s; n = len(s)
i, ans = 0, 0
while i < n//2:
    ans = i
    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
    while i <= k: i += j - k
return s[ans : ans + n//2]

Python 实现

# -*- coding: utf-8 -*-
# Duval 算法：O(n) 求 Lyndon 分解

def duval(s):
    """返回 s 的 Lyndon 分解（块列表，字典序非严格递减）。"""
    n, i = len(s), 0
    fac = []
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i               # s2+s[j] 成为新的 Lyndon 串
            else:
                k += 1
            j += 1
        while i <= k:               # 截出循环节长度 j-k
            fac.append(s[i:i + j - k])
            i += j - k
    return fac


def is_lyndon(s):
    """判断 s 是否为 Lyndon 串（严格小于所有非平凡后缀）。"""
    return all(s < s[i:] for i in range(1, len(s)))


def min_cyclic_shift_duval(s):
    """最小循环移位：对 ss 做 Duval，跨中点的 Lyndon 块起点即答案。"""
    ss = s + s
    n = len(ss)
    i, ans = 0, 0
    while i < n // 2:
        ans = i
        j, k = i + 1, i
        while j < n and ss[k] <= ss[j]:
            if ss[k] < ss[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            i += j - k
    return ss[ans:ans + n // 2]


if __name__ == '__main__':
    # 分解性质验证：每个块是 Lyndon 串且块字典序非严格递减，拼接还原
    for s in ['ababab', 'aaaa', 'ababac', 'banana', 'aababbababb']:
        fac = duval(s)
        assert ''.join(fac) == s
        assert all(is_lyndon(w) for w in fac)
        assert all(fac[i] >= fac[i + 1] for i in range(len(fac) - 1)), fac
    assert duval('ababab') == ['ab', 'ab', 'ab']
    assert duval('aaaa') == ['a', 'a', 'a', 'a']
    # 最小循环移位与暴力对拍
    import random
    random.seed(0)
    for _ in range(300):
        n = random.randint(1, 10)
        t = ''.join(random.choice('abc') for _ in range(n))
        shifts = [t[i:] + t[:i] for i in range(n)]
        assert min_cyclic_shift_duval(t) == min(shifts), (t, min_cyclic_shift_duval(t), min(shifts))
    # 分解唯一性：暴力检查所有合法分解（小规模）
    import itertools
    for s in ['aab', 'ababa', 'baba']:
        n = len(s)
        ways = []
        for cut in range(1 << (n - 1)):
            parts, last = [], 0
            for bit in range(n - 1):
                if (cut >> bit) & 1:
                    parts.append(s[last:bit + 1]); last = bit + 1
            parts.append(s[last:])
            if all(is_lyndon(p) for p in parts) and all(parts[i] >= parts[i + 1] for i in range(len(parts) - 1)):
                ways.append(parts)
        assert ways == [duval(s)], (s, ways, duval(s))
    print('lyndon-factorization tests passed')

易错点

• 比较是 s[k] <= s[j] 才继续，s[k] < s[j] 时 k 回 i 而不是 k+=1
• 截块长度是 j-k 不是 j-i，且条件是 while i <= k 而非 i < j
• 最小循环移位的 while 条件 i < n//2，且返回 ss[ans:ans+n//2]
• 分解的块要满足 w_i >= w_{i+1}（非严格递减），验证时注意相等允许
• Lyndon 串要求'严格'小于后缀，全等块（如 aaa）不构成单一 Lyndon 串

例题

信源

• OI Wiki✓ https://oi-wiki.org/string/lyndon/
• CP-Algorithms✓ https://cp-algorithms.com/string/lyndon_factorization.html