Java怎么查找最长公共子串

# Java怎么查找最长公共子串

## 什么是最长公共子串

最长公共子串（Longest Common Substring）是指两个或多个字符串中**连续相同**的最长子串。与最长公共子序列（LCS）不同，子串要求字符必须是连续的。例如：

字符串A: “abcde” 字符串B: “abfde” 最长公共子串: “ab” 或 “de”（长度为2）

## 常见解决算法

### 1. 动态规划法（推荐）

时间复杂度O(n²)，空间复杂度O(n²)，适合中等长度字符串。

```java
public static String longestCommonSubstring(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m+1][n+1];
    int maxLen = 0, endIndex = 0;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    endIndex = i;
                }
            }
        }
    }
    return maxLen == 0 ? "" : s1.substring(endIndex - maxLen, endIndex);
}

2. 后缀自动机法

适合超长字符串（时间复杂度接近O(n)），但实现较复杂。

3. 滑动窗口法

时间复杂度O(n³)，仅适用于很短字符串。

完整示例代码

import java.util.Arrays;

public class LongestCommonSubstring {
    
    public static void main(String[] args) {
        String str1 = "ABABC";
        String str2 = "BABCA";
        System.out.println("最长公共子串: " + findLCS(str1, str2));
    }
    
    public static String findLCS(String s1, String s2) {
        // 边界检查
        if (s1 == null || s2 == null || s1.isEmpty() || s2.isEmpty()) {
            return "";
        }
        
        // 动态规划表
        int[][] dp = new int[s1.length()+1][s2.length()+1];
        int maxLength = 0;
        int endPos = 0;
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        endPos = i;
                    }
                }
            }
        }
        
        return maxLength > 0 ? 
               s1.substring(endPos - maxLength, endPos) : "";
    }
}

算法优化建议

1. 空间优化：可将二维数组优化为一维数组

   int[] dp = new int[n+1];
   // 需要额外变量保存左上角的值
   

2. 提前终止：当剩余长度不可能超过当前maxLen时可提前break

3. 并行计算：对于超大字符串可使用分治+并行处理

处理多个字符串的情况

当需要处理N个字符串时，可以采用：

1. 两两计算法：先计算前两个的LCS，再与第三个计算…
2. 广义后缀树：适合大量字符串但实现复杂

// 多字符串LCS示例
public static String findMultiLCS(String... strings) {
    if (strings.length == 0) return "";
    String lcs = strings[0];
    for (int i = 1; i < strings.length; i++) {
        lcs = findLCS(lcs, strings[i]);
        if (lcs.isEmpty()) break;
    }
    return lcs;
}

实际应用场景

1. DNA序列比对
2. 代码相似性检测
3. 文档抄袭检查
4. 版本控制系统中的差异分析

注意事项

1. 区分大小写：根据需求决定是否要统一大小写
2. 中文处理：注意一个中文字符可能占多个char
3. 性能瓶颈：字符串过长时需考虑内存限制

扩展阅读

• Suffix Automaton
• Hirschberg’s Algorithm
• Java String API

”`