JAVA 实现 Longest Common Subsequence（最长公共子序列，LCS）算法

一、项目背景详细介绍

最长公共子序列（Longest Common Subsequence，简称 LCS）是字符串算法中一个非常基础且重要的问题。给定两个序列（字符串、字符数组或一般序列） A 和 B，LCS 问题要求找出一个在 A 与 B 中都出现且长度最长的子序列（注意：子序列不要求连续，只要求相对顺序保持）。LCS 的研究有非常广泛的应用场景，包括但不限于：

• 版本控制与差异比较（diff）——基于 LCS 可以找出两个文件的最长公共部分，从而定位插入/删除差异；

• 文本相似度度量——通过 LCS 长度可以衡量两个字符串的相似程度；

• 生物信息学——DNA / 蛋白质序列比对中常用到类似的序列比对算法（LCS 是教学中的基础）；

• 文本编辑器与自动补全系统——在某些排序和提示逻辑中可借助子序列匹配；

• 动态规划教学——LCS 是讲解二维动态规划（表格填充、回溯重建、复杂度分析）的经典案例。

LCS 的标准解法是动态规划，时间复杂度为 O(n*m)（n、m 分别为两个序列长度），空间复杂度原始实现为 O(n*m)，但可以通过滚动数组把空间复杂度优化到 O(min(n,m))（只计算长度时可用）。此外，LCS 不仅要求返回长度，常见题目还要求返回一个最长公共子序列本身（如果有多个等长解，返回任意一个）。因此在实现时要同时考虑计算长度与重建序列两项功能，并保持代码易读、可复用、易调试。

二、项目需求详细介绍

本项目目标是实现一个功能完备、注释清晰的 Java 工具类/程序来解决 LCS 问题，并满足以下具体需求：

1. 输入 / 输出

   • 输入：两个字符串 s1、s2（也支持一般字符数组或泛化序列）；

   • 输出（至少提供）：

     • int：最长公共子序列的长度；

     • String：返回一个具体的最长公共子序列（若存在多个，返回任意一个）。

2. 实现方式（至少提供三种变体）

   • 自底向上（Bottom-Up）二维 DP：计算并填充 dp 二维表，且支持从 dp 表回溯重建任一 LCS。

   • 空间压缩版本（只求长度）：当只需长度时，用滚动数组将空间降为 O(min(n,m))。

   • 自顶向下（Top-Down + Memo）：递归 + 记忆化实现（便于教学、理解），并保存决策以重建序列。

3. 性能要求与复杂度

   • 标准实现时间复杂度 O(n*m)，空间 O(n*m)；

   • 空间压缩版本时间复杂度仍为 O(n*m)，空间可降为 O(min(n,m))。

4. 健壮性 & 边界处理

   • 处理空串；

   • 能处理任意 ASCII / Unicode 字符串（本文示例使用 Java char）；

   • 输入长度差距较大时保持空间压缩效率。

三、相关技术详细介绍

要实现 LCS，需要理解并掌握以下技术点：

1. 动态规划基础概念

   • LCS 的最优子结构：若两个序列末尾字符相等，则 LCS 可以由 LCS(A[0..i-1], B[0..j-1]) + 1 得到；若不相等，则 LCS(A[0..i-1], B[0..j]) 与 LCS(A[0..i], B[0..j-1]) 的较大值即为 LCS(A[0..i], B[0..j])。

2. 状态与转移方程

   • 定义 dp[i][j] 表示 A[0..i-1] 与 B[0..j-1] 的 LCS 长度（注意此处 dp 通常使用 n+1 × m+1 的表以方便边界处理）。

   • 转移：

     if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

   • 边界：dp[0][j] = dp[i][0] = 0。

3. 回溯重建 LCS

   • 填好 dp 表后，从 i=n, j=m 开始回溯：

     • 若 A[i-1] == B[j-1]，则该字符属于某个 LCS，加入结果（放在结果末端），然后 i--, j--；

     • 否则沿 dp[i-1][j] 与 dp[i][j-1] 的较大值方向移动（若二者相等可任选一边，可能导致不同的等长解）。

   • 逆序收集后再反转得到最终 LCS 字符串。

4. 空间压缩技巧

   • 观察转移方程发现 dp[i][j] 只依赖上一行 dp[i-1][*] 与当前行 dp[i][*] 的左侧值，因此可以使用两行交替或 1D 数组（从右向左或从左向右小心更新）来压缩空间（但压缩后无法直接回溯重建 LCS，只能返回长度）。

5. 自顶向下（记忆化）

   • 用递归 f(i,j) 表示 LCS(A[i..], B[j..])，并用 memo[i][j] 缓存结果，避免重复子问题。可同时保存选择方向以便重建。

6. 复杂度分析

   • 时间复杂度：标准 DP 为 O(n*m)；空间复杂度：O(n*m)（可压缩为 O(min(n,m))）。

四、实现思路详细介绍

我们将按下面思路实现，并在代码中提供清晰分段注释：

1. API 设计

   • 主类 LongestCommonSubsequence 提供以下静态方法：

     • lcsLength(String a, String b)：返回 LCS 长度（二维 DP）；

     • lcs(String a, String b)：返回一个 LCS 字符串（二维 DP + 回溯重建）；

     • lcsLengthSpaceOptimized(String a, String b)：仅返回长度但空间优化为 O(min(n,m))；

     • lcsTopDown(String a, String b)：自顶向下记忆化版本，返回 Result(length, subsequence)；

   • 提供 Result 小类用于封装长度与字符串结果。

2. 实现细节

   • 在二维 DP 实现中使用 int[][] dp = new int[n+1][m+1]；填表顺序为 i 从 1..n，j 从 1..m。

   • 回溯时从 i=n, j=m 向前构造 StringBuilder，遇到匹配字符则 append 并 i--, j--，否则比较 dp[i-1][j] 与 dp[i][j-1] 做决策。

   • 空间压缩版本选取短的字符串作为列以降低内存消耗（即 min(n,m) 的一维数组）。

   • 自顶向下版本使用 memo 初始化为 -1 以区分未计算状态，同时记录 choice（用于重建）。

3. 测试用例

   • 提供小规模与中等规模例子：如 ("ABCBDAB","BDCABA")（经典例子）；("AGGTAB","GXTXAYB") 等，并打印长度与一个 LCS。

   • 验证空串、完全不相同字符串及相等字符串的情况。

五、完整实现代码

// ==========================================
// 文件：LongestCommonSubsequence.java
// 功能：多种实现 LCS（最长公共子序列）
// 包含：二维 DP（长度 + 重建）、空间优化长度、自顶向下（Memo）
// 注：可以直接编译运行： javac LongestCommonSubsequence.java
//     然后： java LongestCommonSubsequence
// ==========================================

import java.util.Arrays;

public class LongestCommonSubsequence {

    /**
     * 返回 LCS 的长度（自底向上二维 DP）
     * 时间 O(n*m)，空间 O(n*m)
     */
    public static int lcsLength(String a, String b) {
        if (a == null || b == null) return 0;
        int n = a.length(), m = b.length();
        if (n == 0 || m == 0) return 0;

        // dp[i][j] 表示 a[0..i-1] 与 b[0..j-1] 的 LCS 长度
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            char ca = a.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char cb = b.charAt(j - 1);
                if (ca == cb) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 返回一个 LCS 字符串（若有多个等长 LCS，返回任意一个）
     * 使用二维 DP 表并回溯重建序列
     */
    public static String lcs(String a, String b) {
        if (a == null || b == null) return "";
        int n = a.length(), m = b.length();
        if (n == 0 || m == 0) return "";

        int[][] dp = new int[n + 1][m + 1];

        // 填表
        for (int i = 1; i <= n; i++) {
            char ca = a.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char cb = b.charAt(j - 1);
                if (ca == cb) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        // 回溯重建（从 dp[n][m] 开始）
        StringBuilder sb = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                // 当前字符属于 LCS
                sb.append(a.charAt(i - 1));
                i--; j--;
            } else {
                // 向 dp 值大的方向移动
                if (dp[i - 1][j] >= dp[i][j - 1]) i--;
                else j--;
            }
        }
        return sb.reverse().toString(); // 因为是从后往前收集的
    }

    /**
     * 空间优化版本：只返回 LCS 长度，空间 O(min(n,m))
     * 思路：将短串作为列，用一维数组交替更新
     */
    public static int lcsLengthSpaceOptimized(String a, String b) {
        if (a == null || b == null) return 0;
        // 让 b 为较短的字符串以降低空间
        if (a.length() < b.length()) {
            String tmp = a; a = b; b = tmp;
        }
        int n = a.length(), m = b.length();
        if (m == 0) return 0;

        int[] dp = new int[m + 1]; // dp[j] 表示当前 i 行对应的值
        for (int i = 1; i <= n; i++) {
            int prev = 0; // prev 存储 dp[i-1][j-1]
            char ca = a.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                int temp = dp[j]; // 保存未更新前的 dp[j]（即上一行的 dp[i-1][j]）
                char cb = b.charAt(j - 1);
                if (ca == cb) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]); // dp[j] (上行) vs dp[j-1] (本行左)
                }
                prev = temp; // 更新 prev 为下一列的 dp[i-1][j-1]
            }
        }
        return dp[m];
    }

    /**
     * 自顶向下（递归 + 记忆化）版本，返回 Result（长度 + 一个具体子序列）
     * 该实现同时保存选择以便回溯重建
     */
    public static Result lcsTopDown(String a, String b) {
        if (a == null || b == null) return new Result(0, "");
        int n = a.length(), m = b.length();
        if (n == 0 || m == 0) return new Result(0, "");

        int[][] memo = new int[n][m]; // memo[i][j] 表示 a[i..] 与 b[j..] 的 LCS 长度
        for (int[] row : memo) Arrays.fill(row, -1);
        int[][] choice = new int[n][m]; // 0=unset,1=match both,2=skip a[i],3=skip b[j]

        int len = dfs(a, b, 0, 0, memo, choice);
        // 基于 choice 重建一个 LCS
        String subseq = reconstructFromChoice(a, b, choice);
        return new Result(len, subseq);
    }

    // 递归函数：从 (i,j) 开始计算 a[i..], b[j..] 的 LCS 长度
    private static int dfs(String a, String b, int i, int j, int[][] memo, int[][] choice) {
        int n = a.length(), m = b.length();
        if (i >= n || j >= m) return 0;
        if (memo[i][j] != -1) return memo[i][j];

        if (a.charAt(i) == b.charAt(j)) {
            int res = 1 + dfs(a, b, i + 1, j + 1, memo, choice);
            memo[i][j] = res;
            choice[i][j] = 1; // match
            return res;
        } else {
            int skipA = dfs(a, b, i + 1, j, memo, choice);
            int skipB = dfs(a, b, i, j + 1, memo, choice);
            if (skipA >= skipB) {
                memo[i][j] = skipA;
                choice[i][j] = 2; // skip a[i]
            } else {
                memo[i][j] = skipB;
                choice[i][j] = 3; // skip b[j]
            }
            return memo[i][j];
        }
    }

    // 根据 choice 表从 (0,0) 构造一个 LCS（可能存在多个等长解，这里按 choice 指示）
    private static String reconstructFromChoice(String a, String b, int[][] choice) {
        StringBuilder sb = new StringBuilder();
        int i = 0, j = 0;
        int n = a.length(), m = b.length();
        while (i < n && j < m) {
            if (choice[i][j] == 0) break; // 未记录（可能到达边界）
            if (choice[i][j] == 1) {
                sb.append(a.charAt(i));
                i++; j++;
            } else if (choice[i][j] == 2) {
                i++;
            } else if (choice[i][j] == 3) {
                j++;
            } else break;
        }
        return sb.toString();
    }

    // 结果类：保存长度与一个具体的子序列
    public static class Result {
        public final int length;
        public final String subsequence;
        public Result(int length, String subsequence) {
            this.length = length;
            this.subsequence = subsequence;
        }
        @Override
        public String toString() {
            return "length=" + length + ", subsequence=\"" + subsequence + "\"";
        }
    }

    // 简单测试（主方法）
    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCABA";
        System.out.println("=== 基本示例 ===");
        System.out.println("A = " + s1);
        System.out.println("B = " + s2);
        System.out.println("LCS 长度（二维 DP）: " + lcsLength(s1, s2));
        System.out.println("LCS（字符串）        : " + lcs(s1, s2));
        System.out.println("LCS 长度（空间优化）: " + lcsLengthSpaceOptimized(s1, s2));
        System.out.println("LCS 自顶向下结果     : " + lcsTopDown(s1, s2));

        // 更多测试
        String a = "AGGTAB";
        String b = "GXTXAYB";
        System.out.println("\n=== 额外示例 ===");
        System.out.println("A = " + a);
        System.out.println("B = " + b);
        System.out.println("LCS 长度: " + lcsLength(a, b));
        System.out.println("LCS: " + lcs(a, b));
        System.out.println("TopDown: " + lcsTopDown(a, b));

        // 边界情况
        System.out.println("\n=== 边界情况 ===");
        System.out.println("空串 vs 任意串: " + lcs("", "ABCDE"));
        System.out.println("完全相同: " + lcs("ABCDE", "ABCDE"));
        System.out.println("无公共字符: " + lcs("ABC", "DEF"));
    }
}

六、代码详细解读

1. lcsLength(String a, String b)

   • 作用：使用经典的自底向上二维动态规划计算并返回两个字符串 a 与 b 的最长公共子序列长度（不返回序列本身）。该方法构建 dp 表并按 i=1..n, j=1..m 填表，最终返回 dp[n][m]。

2. lcs(String a, String b)

   • 作用：基于二维 dp 表同时实现长度计算与回溯重建，返回一个具体的 LCS（如果存在多个等长的 LCS，则返回其中任意一个）。回溯过程从表的右下角 dp[n][m] 开始，按照匹配或取较大方向的规则向左上回溯，收集字符后逆序输出。

3. lcsLengthSpaceOptimized(String a, String b)

   • 作用：当只需 LCS 长度而不需要重建序列时，使用空间压缩技术将空间复杂度降到 O(min(n,m))。该方法确保较短的字符串作为列以最小化一维数组长度，并通过 prev/temp 保存临时状态以正确更新。

4. lcsTopDown(String a, String b)

   • 作用：提供自顶向下（递归 + 记忆化）的实现。它初始化 memo 与 choice 两个二维数组，调用递归 dfs 填充 memo（避免重复计算）并用 choice 记录每个状态的决策，最后调用重建函数生成一个 LCS 字符串并以 Result 返回长度与序列。

5. dfs(String a, String b, int i, int j, int[][] memo, int[][] choice)

   • 作用：自顶向下的递归核心函数，计算 a[i..] 和 b[j..] 的 LCS 长度，使用 memo 缓存结果并将决策记录到 choice（1=匹配、2=跳过 a、3=跳过 b），以便后续重建。

6. reconstructFromChoice(String a, String b, int[][] choice)

   • 作用：基于 choice 表从 (0,0) 开始沿记录的决策路径构建一个 LCS；当 choice 表到达未记录位置或边界时结束。此方法适配自顶向下实现。

7. Result 内部类

   • 作用：作为返回结果的简单数据结构，封装 LCS 的长度与其中一个具体子序列字符串，便于统一返回并打印。

8. main 方法

   • 作用：提供一系列示例性测试用例（经典教材例子、额外样例、边界情况），演示各个方法的输出与差异，便于用户验证正确性与理解算法差别。

七、项目详细总结

• 本文完整实现并讲解了求解 最长公共子序列（LCS） 的多种方法：

  1. 自底向上二维 DP（既能求长度也能回溯得到序列）；

  2. 空间压缩的一维 DP（只求长度、空间 O(min(n,m))）；

  3. 自顶向下递归 + 记忆化（便于教学并可记录决策以重建序列）。

• 各种实现的适用场景：

  • 需要序列本身时使用二维 DP（回溯重建）；

  • 只需长度且内存敏感时使用空间压缩版本；

  • 教学或需要按递归思路逐步理解子问题时可采用自顶向下方法。

• 算法复杂度：时间 O(n*m)（不可避免），空间 O(n*m)（可压缩到 O(min(n,m))）。当序列长度非常大（比如几百万）时，标准 DP 已不现实，这时需借助近似算法、后向索引、或特定领域（如生物信息学）的优化方法（例如通用比对算法、后缀数组/树、或启发式剪枝）。

八、项目常见问题及解答（FAQ）

1. Q：LCS 和 Longest Common Substring（最长公共子串）有什么区别？

   • A：子序列（subsequence）允许不连续但保持相对顺序；子串（substring）要求连续。两者问题与解法不同，最长公共子串可以用后缀数组、后缀自动机或动态规划（O(n*m)）解决，而 LCS 常用二维 DP。

2. Q：为什么空间优化后无法直接重建序列？

   • A：因为重建需要完整的 dp 表（或等价的决策信息）。在只保存一维数组的情况下我们丢失了回溯所需的历史状态，因此只能得到长度。若要在低空间下重建序列，需要额外策略（例如分治法 Hirschberg 算法），该算法可以在 O(n*m) 时间内把空间降到 O(min(n,m)) 并同时支持序列重建（实现较复杂，适合需要极端内存优化时使用）。

3. Q：lcs 方法返回的序列是唯一的吗？

   • A：不一定。如果存在多个等长 LCS，二维 DP 的回溯规则会选择其中一种（通常偏向上或左方向），不同回溯策略可能得到不同的等长 LCS。题目通常允许任意一个。

4. Q：自顶向下和自底向上哪种更好？

   • A：两者时间复杂度相同。自底向上更适合迭代实现、空间压缩和非递归环境；自顶向下更贴近递归定义、便于按需计算和教学演示。工程上倾向于自底向上实现以避免递归栈深度问题。

5. Q：能否把 LCS 应用到多字符串（多于两个）情形？

   • A：多序列的最长公共子序列（MSCS）问题可以定义，但求解复杂度随序列数目呈指数增长（DP 需要高维表），通常只在序列数量非常少时可行。现实中常用逐对合并或启发式方法。

6. Q：有什么更高效的替代方法？

   • A：对于通用 LCS 问题，时间下界仍为 O(n*m)（在比较模型下）。针对特定场景（比如小字母表、稀疏匹配），可用位集（bitset）优化或后缀自动机等技巧获得实用加速。

九、扩展方向与性能优化

1. Hirschberg 算法（空间分治）

   • 该算法可在 O(n*m) 时间与 O(min(n,m)) 空间下重建 LCS，适合内存受限但又需要序列本身的场景。实现利用分治与两个方向的 LCS 长度计算拼接中点。

2. 位运算优化（bitset 技巧）

   • 若字符集较小或可映射到位集，可用位运算将 DP 并行化（例如 Myers 的 bit-parallel LCS 算法），在常数因子上大幅提速。

3. 后缀结构与高级索引

   • 对于长文本与多个查找，后缀数组/树、后缀自动机等索引可用于相关字符串问题，但对一般 LCS 并非直接替代品。

4. 并行/分布式计算

   • 对于极大规模的输入，可尝试把计算矩阵分块并并行计算，但要注意依赖关系和边界合并。

5. 应用级优化

   • 在差异比较（diff）工具中，先做快速启发式过滤（例如行哈希、最长公共子串预判）再精确 LCS 计算，以减少 DP 工作量。