题解 | 【模板】马拉车算法

import java.io.*;

public class Main {
     public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入，PrintWriter输出结果，提高IO效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取输入字符串并去除首尾空格
        String s = br.readLine().trim();

        // 处理空字符串或null值的情况
        if (s == null || s.length() == 0) {
            out.println(0);  // 输出0
            out.flush();     // 确保所有输出都被刷新
            return;          // 提前返回
        }

        // 调用manacher算法处理字符串并输出结果
        out.println(manacher(s));
        out.flush();  // 刷新输出缓冲区
        out.close();  // 关闭输出流
        br.close();   // 关闭输入流
    }

    /**
     * Manacher算法实现，用于查找字符串中的最长回文子串的长度
     * 该算法通过预处理字符串和利用回文对称性来高效地找到最长回文子串
     *
     * @param s 输入的字符串
     * @return 返回最长回文子串的长度
     */
    private static int manacher(String s) {
        // 构造新的字符串，以^开头，$结尾，并在每个字符间插入#，这样可以统一处理奇数和偶数长度的回文
        StringBuilder sb = new StringBuilder("^");

        // 在原字符串的每个字符前后添加特殊字符#
        for (char c : s.toCharArray()) {
            sb.append("#").append(c);
        }

        // 添加结尾标记
        sb.append("#$");

        // 将构造好的字符串转换为字符数组
        char[] t = sb.toString().toCharArray();

        // 获取新字符串的长度
        int n = t.length;
        // 创建数组p，p[i]表示以t[i]为中心的最长回文半径
        int[] p = new int[n];
        // c表示当前回文中心，r表示当前回文右边界
        int c = 0, r = 0;
        // 记录最长回文半径
        int maxLen = 0;

        // 遍历字符串，跳过首尾的特殊字符
        for (int i = 1; i < n - 1; i++) {
            // 利用回文对称性，如果i在当前回文范围内，则获取其对称位置的回文半径
            p[i] = r > i ? Math.min(r - i, p[2 * c - i]) : 0;

            // 尝试扩展以i为中心的回文
            while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
                p[i]++;
            }

            // 如果当前回文右边界超过了r，更新中心和右边界
            if (i + p[i] > r) {
                c = i;
                r = i + p[i];
            }

            // 更新最大回文半径
            maxLen = Math.max(maxLen, p[i]);
        }

        // 返回最长回文半径，也就是最长回文子串的长度
        return maxLen;
    }
}