Java 尋找文本中最長回文子串 (USACO calfflac 題目解法)

前言

USACO 經典題目 calfflac：讀取文本檔，忽略非字母、不分大小寫，找出最長回文子串，輸出長度與原文對應片段。本文提供 O(N²) 中心展開法 Java 實作，含完整原始碼與關鍵技巧解析。

演算法策略：中心展開法

1. 預處理：提取所有字母存入 letters (StringBuilder)，並記錄每個字母在原文的索引 indexes[]
2. 遍歷每個字母作為中心點，嘗試奇數長度 (單中心) 與偶數長度 (雙中心) 回文
3. 以 maxLength 紀錄目前最長，maxIndex 紀錄中心索引
4. 最後透過 indexes[] 映射回原文區間輸出

完整原始碼

import java.util.*;
import java.io.*;

class calfflac {
    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new FileReader("calfflac.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("calfflac.out")));

        StringBuilder origin = new StringBuilder(20000);
        StringBuilder letters = new StringBuilder(20000);
        int[] indexes = new int[20000];
        String temp;
        while ((temp = f.readLine()) != null) {
            origin.append(temp).append('\n');
        }
        int len = origin.length();
        for (int i = 0; i < len; i++) {
            char c = origin.charAt(i);
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                letters.append(c);
                indexes[letters.length() - 1] = i;
            }
        }

        int maxLength = 1, maxIndex = 0;
        len = letters.length();
        for (int i = 0; i < len; i++) {
            int length = maxLength + 1; // 只找更長的，同長保留最早
            boolean isChanged = false; // 切換奇/偶數長度
            for (; i - (length - 1) / 2 >= 0 && i + length / 2 < len; ) {
                if (isPal(letters, i - (length - 1) / 2, i + length / 2)) {
                    maxLength = length;
                    maxIndex = i;
                    length += 2;
                } else if (!isChanged) {
                    isChanged = true;
                    length++; // 奇->偶 或 偶->奇
                } else break;
            }
        }

        int start = indexes[maxIndex - (maxLength - 1) / 2];
        int end = indexes[maxIndex + maxLength / 2];
        String result = origin.substring(start, end + 1);
        out.println(maxLength);
        out.println(result);
        out.flush(); out.close(); System.exit(0);
    }

    // 判斷 s[i..j] 是否為回文 (不分大小寫)
    static boolean isPal(StringBuilder s, int i, int j) {
        for (; i < j; i++, j--) {
            char c1 = s.charAt(i), c2 = s.charAt(j);
            if (c1 != c2 && (c1 - c2) % 32 != 0) return false; // ASCII 大小寫差 32
        }
        return true;
    }
}

關鍵技巧解析

複雜度分析

• 時間：O(N²) — N 為字母數，每中心點最多展開 O(N)
• 空間：O(N) — 儲存 letters、indexes

優化方向

1. Manacher 演算法 O(N) 線性時間 (較複雜，競程常用)
2. 後綴自動機/後綴陣列 O(N log N)
3. 實務中文本較短 O(N²) 足夠，且程式碼簡潔易維護

測試範例

輸入 (calfflac.in):
"Hello, World! Madam, I'm Adam."

輸出 (calfflac.out):
11
"Madam, I'm Adam"