HDU 1238 最長公共子串問題：正反向匹配 Java 實現詳解

問題背景

HDU 1238 是一道經典的最長公共子串問題，難點在於不僅要考慮正向匹配，還需處理反向（逆序）匹配的情況。給定多組字符串，需找出在所有字符串中都出現的最長子串（含正向與反向）。

解題思路

1. 獲取最短字符串：從每組測試數據中找出長度最短的字符串作為基準，減少枚舉範圍
2. 構建反向字符串：對每個輸入字符串生成其逆序版本，用於反向匹配
3. 枚舉所有子串：從最短字符串中枚舉所有可能的子串
4. 雙向驗證：對每個子串，同時在原字符串組和反向字符串組中檢查是否全包含
5. 記錄最大長度：滿足條件的子串中取最長者

核心代碼實現

package D0710;

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[] strRev = new String[n];
            
            // 讀入並構建反向字符串
            for (int i = 0; i < n; i++) {
                str[i] = sc.next();
                strRev[i] = new StringBuffer(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 maxLen = getMaxCommonLen(shortest, str, strRev);
            System.out.println(maxLen);
        }
    }
    
    private static int getMaxCommonLen(String base, String[] strs, String[] revStrs) {
        int n = strs.length;
        int len = base.length();
        String best = "";
        
        // 枚舉所有子串
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                String sub = base.substring(i, j);
                
                // 正向匹配檢查
                boolean ok = true;
                for (String s : strs) {
                    if (!s.contains(sub)) {
                        ok = false;
                        break;
                    }
                }
                if (ok && sub.length() > best.length()) {
                    best = sub;
                }
                
                // 反向匹配檢查
                ok = true;
                for (String s : revStrs) {
                    if (!s.contains(sub)) {
                        ok = false;
                        break;
                    }
                }
                if (ok && sub.length() > best.length()) {
                    best = sub;
                }
            }
        }
        return best.length();
    }
}

關鍵點總結

• 使用 StringBuffer.reverse() 快速構建反向字符串
• 以最短字符串為基準枚舉子串，時間複雜度相對可控
• 正向與反向分別檢查，滿足任一條件即可
• 利用 String.contains() 簡化子串判斷邏輯