Java 實作尋找兩字串最長公共子串演算法詳解

前言

在程式設計面試與演算法練習中，「最長公共子串」是經典題目之一。本文將以 Java 為例，詳細解析如何在華為 OJ 線上評測系統的限制下，實作求解兩個字串最長公共子串長度的程式碼，並說明關鍵邏輯與優化方向。

華為 OJ Java 提交規範

在華為 OJ 平台使用 Java 提交代碼時，必須遵守三項硬性規定，否則會導致編譯失效或測試用例無法通過：

• 禁止套件宣告：程式碼中不能出現 package 關鍵字。
• 主類別名固定為 Main：包含 main 方法的公開類別必須命名為 Main。
• 嚴禁輸出多餘資訊：標準輸出僅能包含題目要求的結果，不得輸入提示、除錯訊息等額外內容。

核心演算法思路

本範例採用「暴力枚舉 + 剪枝」策略，核心步驟如下：

1. 將兩字串統一轉為小寫，忽略大小寫差異。
2. 識別長短字串，以較短者為基準枚舉子串，減少比較次數。
3. 從最長可能長度遞減至 1，對短字串的所有該長度子串進行遍歷。
4. 在長字串中檢查是否存在相同子串，一旦發現即返回當前長度（即為最長公共子串長度）。
5. 若所有長度均無匹配，返回 0。

完整程式碼實作

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main mainObj = new Main();
        int len = mainObj.getCommonStrLength(sc.next(), sc.next());
        System.out.println(len);
    }

    int getCommonStrLength(String str1, String str2) {
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        int len1 = str1.length();
        int len2 = str2.length();
        String min = null, max = null;
        min = len1 <= len2 ? str1 : str2;
        max = len1 > len2 ? str1 : str2;

        // 外層迴圈：子串長度從長到短
        for (int i = min.length(); i >= 1; i--) {
            // 中層迴圈：遍歷短字串所有長度為 i 的子串
            for (int j = 0; j <= min.length() - i; j++) {
                String target = min.substring(j, j + i);
                // 內層迴圈：在長字串中尋找相同子串
                for (int k = 0; k <= max.length() - i; k++) {
                    if (max.substring(k, k + i).equals(target)) {
                        return i; // 找到即返回，保證是最長
                    }
                }
            }
        }
        return 0;
    }
}

複雜度分析與優化建議

上述解法時間複雜度為 O(n³)（n 為短字串長度），空間複雜度 O(1)。雖能通過基礎測試，但在長字串場景下效能不足。實務開發中建議採用：

• 動態規劃：建立二維 DP 表，時間/空間複雜度均為 O(m×n)，可進一步優化空間至 O(min(m,n))。
• 後綴自動機/後綴陣列：可達線性時間 O(m+n)，適合超大規模字串處理。
• 二分查找 + 滾動雜湊 (Rabin-Karp)：時間複雜度 O((m+n) log min(m,n))，工程落地較簡單。

總結

本文展示了在特定 OJ 限制下的 Java 基礎實作，幫助開發者理解題目邏輯與提交規範。實際專案中應根據資料規模選擇更優演算法，平衡開發效率與執行效能。