最长公共子序列 (Longest Common Subsequence, LCS)

算法原理

最长公共子序列（LCS）问题是动态规划中的经典问题之一。给定两个序列，LCS问题是找出这两个序列的最长公共子序列的长度。子序列是指在不改变字符相对顺序的情况下，通过删除某些字符（也可以不删除）得到的新序列。与子串不同，子序列中的字符不需要连续。LCS问题广泛应用于版本控制系统（如Git）、生物信息学（DNA序列比对）和文本相似度计算等领域。

算法步骤

1. 创建一个二维数组dp，其中dp[i][j]表示第一个序列的前i个字符和第二个序列的前j个字符的LCS长度
2. 初始化dp数组，第0行和第0列都为0
3. 对于每个字符位置i和j，计算：
   • 如果两个字符相同，即str1[i-1] == str2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
   • 如果两个字符不同，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. dp[m][n]即为两个序列的LCS长度
5. 通过回溯dp数组可以构造出具体的LCS字符串

代码实现

public class LCS {
    // 计算最长公共子序列的长度
    public static int lcsLength(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        
        // 创建dp表
        int[][] dp = new int[m + 1][n + 1];
        
        // 填充dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果字符相同
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    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[m][n];
    }
    
    // 构造最长公共子序列
    public static String lcsString(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        
        // 创建dp表
        int[][] dp = new int[m + 1][n + 1];
        
        // 填充dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 回溯构造LCS字符串
        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        
        while (i > 0 && j > 0) {
            // 如果字符相同，加入结果并同时向前移动
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            }
            // 否则向dp值较大的方向移动
            else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        // 因为是从后往前构造的，需要反转
        return lcs.reverse().toString();
    }
    
    // 空间优化版本
    public static int lcsLengthOptimized(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        
        // 只使用两行来节省空间
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            
            // 交换prev和curr
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[n];
    }

    // 测试方法
    public static void main(String[] args) {
        String str1 = "ABCDGH";
        String str2 = "AEDFHR";
        
        System.out.println("字符串1: " + str1);
        System.out.println("字符串2: " + str2);
        
        int length = lcsLength(str1, str2);
        System.out.println("\n最长公共子序列的长度: " + length);
        
        String lcs = lcsString(str1, str2);
        System.out.println("最长公共子序列: " + lcs);
        
        int lengthOpt = lcsLengthOptimized(str1, str2);
        System.out.println("优化版本计算的长度: " + lengthOpt);
        
        // 另一个例子
        String str3 = "AGGTAB";
        String str4 = "GXTXAYB";
        
        System.out.println("\n\n字符串1: " + str3);
        System.out.println("字符串2: " + str4);
        
        int length2 = lcsLength(str3, str4);
        System.out.println("最长公共子序列的长度: " + length2);
        
        String lcs2 = lcsString(str3, str4);
        System.out.println("最长公共子序列: " + lcs2);
    }
}

应用场景

• 版本控制：比较文件的不同版本，找出变化的部分
• 生物信息学：DNA序列比对，找出基因序列的相似性
• 文本处理：计算两个文档的相似度
• 数据压缩：在某些压缩算法中用于寻找重复模式
• 拼写检查：找出用户输入与词典中最相似的单词

优缺点