HDU 1238：最長公共子串（含反向匹配）Java 解法詳解

問題描述

給定 N 條字串，找出在所有字串中都出現的最長子串。特殊條件：子串的反向字串若也在所有字串中出現，同樣視為合法。輸出最大長度。

核心思路

1. 找出最短字串 s（候選子串必來自此字串）。
2. 枚舉 s 的所有子串 sub。
3. 對每個 sub，檢查：
     ① 正向：所有字串是否皆含 sub
     ② 反向：所有字串的反向是否皆含 sub
     兩者滿足任一即為合法。
4. 記錄最長合法子串長度。

完整 Java 實作

import java.util.Scanner;

public class HDU1238 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            String[] str = new String[n];
            String[] rev = new String[n];
            // 讀入並預計算反向字串
            for (int i = 0; i < n; i++) {
                str[i] = sc.next();
                rev[i] = new StringBuilder(str[i]).reverse().toString();
            }
            // 找最短字串
            String shortest = str[0];
            for (int i = 1; i < n; i++)
                if (str[i].length() < shortest.length()) shortest = str[i];
            // 計算最長公共子串長度
            int ans = getMaxLen(shortest, str, rev);
            System.out.println(ans);
        }
    }

    private static int getMaxLen(String s, String[] str, String[] rev) {
        int maxLen = 0;
        int L = s.length();
        // 枚舉所有子串 s[i..j)
        for (int i = 0; i < L; i++) {
            for (int j = i + 1; j <= L; j++) {
                String sub = s.substring(i, j);
                // 剪枝：子串長度不超過當前最大值則跳過
                if (sub.length() <= maxLen) continue;
                boolean ok = true;
                // 正向檢查
                for (String x : str) if (!x.contains(sub)) { ok = false; break; }
                if (ok) { maxLen = sub.length(); continue; }
                // 反向檢查
                ok = true;
                for (String x : rev) if (!x.contains(sub)) { ok = false; break; }
                if (ok) maxLen = sub.length();
            }
        }
        return maxLen;
    }
}

關鍵優化點

• 最短字串作為基準：減少枚舉空間，時間複雜度從 O(N·L³) 降為 O(N·L²·L_min)。
• 預計算反向字串：避免重複反轉，空間換時間。
• 剪枝：僅檢查長度大於當前最大值的子串。
• 提前跳出：任一字串不含目標子串即中斷內層迴圈。

複雜度分析

• 時間：O(N · L_min² · L_avg) —— N 為字串數，L_min 為最短字串長度，L_avg 為平均長度。
• 空間：O(N · L_avg) —— 儲存原字串與反向字串。

進階延伸

若字串長度較大（> 1000），可改用後綴自動機 (SAM)或二分長度 + 雙向哈希將複雜度降至 O(N · L log L)。本題資料範圍下暴力枚舉配合剪枝即可通過。