每日算法 — 使用java实现Lyndon分解：Duval算法与字符串周期性分析

Lyndon 词的定义

Lyndon 词是指严格小于其所有非平凡后缀的字符串。形式化地说，字符串 w 是 Lyndon 词当且仅当对于所有真后缀 v（v 不等于 w），都有 w 小于 v（按字典序）。

例如：
– a、b、ab、aab、abb 是 Lyndon 词
– aa、ba、abab 不是 Lyndon 词（aa 等于后缀 a，ba 大于 a，abab 有后缀 ab 小于 abab）

Lyndon 分解定理

Chen-Fox-Lyndon 定理指出：任意字符串都可以被唯一地分解为一系列 Lyndon 词的拼接，且这些 Lyndon 词按字典序非增排列。

例如：abacabadabacabae 可以唯一分解为：abacabadabacabae（本身就是一个 Lyndon 词）

而 banana 分解为：b · an · an · a

Duval 算法

Jean-Pierre Duval 于 1983 年提出了线性时间 O(n) 的 Lyndon 分解算法。算法的核心思想是利用三个指针 i、j、k 维护当前正在处理的 Lyndon 因子：

• i：当前 Lyndon 因子的起始位置
• j：当前比较位置（i 的后缀与 i+k 的后缀比较）
• k：已匹配的字符数

算法流程

1. 初始化 i = 0
2. 设 j = i + 1, k = i
3. 比较 s[j] 与 s[k]：
4. s[j] == s[k]：j++, k++，继续比较
5. s[j] > s[k]：j = i + 1, k = i，重新开始比较
6. s[j] < s[k]：找到了一个 Lyndon 词，重复输出
7. 输出所有 Lyndon 词后，i = j

Java 实现

基础 Duval 算法

import java.util.ArrayList;
import java.util.List;

public class LyndonFactorization {

    /**
     * Duval 算法：计算字符串的 Lyndon 分解
     * @param s 输入字符串
     * @return Lyndon 词列表（按非增字典序）
     */
    public static List<String> duvalFactorization(String s) {
        List<String> factors = new ArrayList<>();
        int n = s.length();
        int i = 0;

        while (i < n) {
            int j = i + 1;
            int k = i;

            // 寻找以 i 开头的最长 Lyndon 前缀
            while (j < n && s.charAt(k) <= s.charAt(j)) {
                if (s.charAt(k) < s.charAt(j)) {
                    // 发现更大字符，重置 k
                    k = i;
                } else {
                    // 相等，继续比较
                    k++;
                }
                j++;
            }

            // 计算 Lyndon 词的长度
            int len = j - k;

            // 输出重复的 Lyndon 词
            while (i + len <= j) {
                factors.add(s.substring(i, i + len));
                i += len;
            }
        }

        return factors;
    }

    public static void main(String[] args) {
        String[] tests = {
            "banana",
            "abcd",
            "aaaa",
            "abacabadabacabae",
            "mississippi"
        };

        for (String test : tests) {
            List<String> factors = duvalFactorization(test);
            System.out.println(test + " -> " + factors);
        }
    }
}

返回起止位置的优化版本

public class LyndonFactorizationOptimized {

    static class Factor {
        int start, end;
        Factor(int s, int e) { start = s; end = e; }
        public String toString() { return "[" + start + "," + end + ")"; }
    }

    /**
     * 返回 Lyndon 分解的因子位置列表，避免多次创建子串
     */
    public static List<Factor> duval(String s) {
        List<Factor> factors = new ArrayList<>();
        int n = s.length();
        int i = 0;

        while (i < n) {
            int j = i + 1;
            int k = i;

            while (j < n && s.charAt(k) <= s.charAt(j)) {
                if (s.charAt(k) < s.charAt(j)) {
                    k = i;
                } else {
                    k++;
                }
                j++;
            }

            int len = j - k;
            while (i + len <= j) {
                factors.add(new Factor(i, i + len));
                i += len;
            }
        }

        return factors;
    }

    /**
     * 获取字典序最小循环移位（利用 Lyndon 分解）
     */
    public static int minCyclicShift(String s) {
        String ss = s + s;
        int n = s.length();
        List<Factor> factors = duval(ss);

        for (Factor f : factors) {
            if (f.start < n && f.end > f.start) {
                return f.start;
            }
        }
        return 0;
    }
}

De Bruijn 序列构造

public class DeBruijnSequence {

    /**
     * 利用 Lyndon 词构造 De Bruijn 序列
     * De Bruijn 序列 B(k, n) 是一个循环序列，包含所有长度为 n 的 k 进制串恰好一次
     */
    public static String deBruijn(int k, int n) {
        StringBuilder sequence = new StringBuilder();
        // 生成所有长度为 n 的 k 进制 Lyndon 词，且长度整除 n
        generateLyndon("", k, n, sequence);
        return sequence.toString();
    }

    private static void generateLyndon(String prefix, int k, int n, StringBuilder result) {
        if (n == 0) {
            if (isLyndon(prefix)) {
                result.append(prefix);
            }
            return;
        }
        for (int i = 0; i < k; i++) {
            generateLyndon(prefix + (char)('0' + i), k, n - 1, result);
        }
    }

    private static boolean isLyndon(String s) {
        int n = s.length();
        for (int i = 1; i < n; i++) {
            String suffix = s.substring(i);
            if (s.compareTo(suffix) >= 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 更高效的 De Bruijn 序列构造（利用 Lyndon 分解性质）
     */
    public static String deBruijnEfficient(int k, int n) {
        StringBuilder sequence = new StringBuilder();
        char[] a = new char[k * n];
        java.util.Arrays.fill(a, '0');
        deBruijnHelper(a, 1, 1, k, n, sequence);
        return sequence.toString();
    }

    private static void deBruijnHelper(char[] a, int t, int p, int k, int n, StringBuilder sequence) {
        if (t > n) {
            if (n % p == 0) {
                for (int i = 1; i <= p; i++) {
                    sequence.append(a[i]);
                }
            }
        } else {
            a[t] = a[t - p];
            deBruijnHelper(a, t + 1, p, k, n, sequence);
            for (int j = a[t - p] + 1; j < '0' + k; j++) {
                a[t] = (char) j;
                deBruijnHelper(a, t + 1, t, k, n, sequence);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("B(2, 3) = " + deBruijnEfficient(2, 3));
        System.out.println("B(2, 4) = " + deBruijnEfficient(2, 4));
    }
}

字符串周期性检测

public class StringPeriodicity {

    /**
     * 利用 Lyndon 分解检测字符串的最小周期
     * 如果字符串 s 可以表示为 t^k（t 重复 k 次），则返回 |t|
     */
    public static int minimalPeriod(String s) {
        List<LyndonFactorizationOptimized.Factor> factors =
            LyndonFactorizationOptimized.duval(s);

        if (factors.size() == 1) {
            // 只有一个 Lyndon 因子，说明字符串本身是 Lyndon 词
            // 此时周期为字符串长度（无更小周期）
            return s.length();
        }

        // 检查所有因子是否相同
        String first = s.substring(factors.get(0).start, factors.get(0).end);
        int period = first.length();

        for (int i = 1; i < factors.size(); i++) {
            String factor = s.substring(factors.get(i).start, factors.get(i).end);
            if (!factor.equals(first)) {
                return s.length(); // 周期不存在
            }
        }

        return period;
    }

    public static void main(String[] args) {
        String[] tests = {"abcabcabc", "abcd", "aaaa", "ababab", "abcabca"};
        for (String test : tests) {
            int p = minimalPeriod(test);
            System.out.println(test + " 最小周期: " + p +
                (p < test.length() ? " (重复 " + (test.length() / p) + " 次)" : " (无周期)"));
        }
    }
}

复杂度分析

应用场景

1. De Bruijn 序列构造：用于 DNA 测序、组合锁设计、密码学
2. 字典序最小循环移位：在模式匹配和生物信息学中查找循环字符串的最小表示
3. 字符串周期性检测：数据压缩（如 Run-Length Encoding 的预处理）
4. 后缀数组构造：作为 SA-IS 等线性时间后缀数组算法的子过程
5. 生物序列分析：DNA/RNA 序列的重复模式识别

总结

Lyndon 分解是字符串算法中的基础工具，其线性时间的 Duval 实现展现了贪心策略在字符串处理中的强大能力。通过将任意字符串唯一分解为 Lyndon 词序列，我们可以高效解决循环移位、周期性检测和 De Bruijn 序列构造等经典问题。掌握 Lyndon 分解有助于深入理解后缀数组、Burrows-Wheeler 变换等更高级的字符串处理技术。