Java 求兩字符串最長公共子串：滑動窗口與動態規劃雙解法

問題定義

給定兩字符串 s1、s2，找出**最長連續公共子串**（非子序列）。例："135adbfg67" 與 "125dbf59" → "dbf"。

解法一：滑動窗口（原文思路優化版）

核心思想

以較短串為基準，窗口長度從 len 遞減至 1；每個長度下滑動窗口，檢查子串是否存在於長串中。首次命中即為最長公共子串。

代碼實現

public static String longestCommonSubstring(String s1, String s2) {
    if (s1 == null || s2 == null) return "";
    // 保證 s1 是長串，s2 是短串
    if (s1.length() < s2.length()) {
        String tmp = s1; s1 = s2; s2 = tmp;
    }

    for (int len = s2.length(); len > 0; len--) {
        for (int start = 0; start + len <= s2.length(); start++) {
            String candidate = s2.substring(start, start + len);
            if (s1.contains(candidate)) {
                return candidate;  // 找到最長，直接返回
            }
        }
    }
    return "";
}

複雜度：時間 O(n²·m) —— contains 底層仍是 O(n·m)；空間 O(1)。適合短串、教學演示。

解法二：動態規劃（標準最優解）

狀態定義

dp[i][j] 表示以 s1[i-1]、s2[j-1] 結尾的最長公共**後綴**長度。

遞推公式

if (s1.charAt(i-1) == s2.charAt(j-1))
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = 0;

代碼實現

public static String lcsDP(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][m + 1];
    int maxLen = 0, endIdx = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; 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];
                    endIdx = i;  // 在 s1 中的結束位置(不含)
                }
            }
        }
    }
    return maxLen == 0 ? "" : s1.substring(endIdx - maxLen, endIdx);
}

複雜度：時間 O(n·m)、空間 O(n·m)；可優化為滾動數組 O(min(n,m)) 空間。

性能對比

擴展：最長公共子序列 (LCS)

若需**不連續**公共子序列，遞推為：

if (s1[i-1] == s2[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]);

掌握兩種模板，字符串匹配問題迎刃而解。