题解 | #密码截取#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line = reader.readLine();
        // 马拉车字符串处理
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < line.length(); ++i) {
            sb.append(line.charAt(i)).append("#");
        }

        // 马拉车子串i位置的字符
        char[] r = sb.toString().toCharArray(); 
        // 马拉车子串i位置的回文子串长度
        int[] p = new int[r.length];

        // localMaxCenter和localMaxRight的定义：从左往右遍历时遇到的所有局部最长回文子串的表达
        int localMaxCenter = 0, localMaxRight = 0; 
        // localMaxCenter和localMaxRight的作用：
        // 基于回文子串内部对称特性，尽可能及时更新局部最长的可覆盖的到i位置的最长回文子串的位置
        // 来充分利用甚至直接使用前期镜像位置的计算成果
        int globalMaxCenter = 0, globalMaxLength = 0;
        for (int i = 0; i < r.length; ++i) {
            // 情况1，当i < localMaxRight时，
            // 确定mirror位置，2 * localMaxCenter - i
            // 情况1a，镜像mirror位置的p值长度 ≤    localMaxRight - i，直接p[i]=p[mirror]
            // 情况1b，镜像mirror位置的p值长度 >    localMaxRight - i，那么
            // 首先p[i]至少有localMaxRight - i这么长
            // 然后继续使用中心扩展法进行进一步的确认g
            p[i] = i < localMaxRight ? Math.min(localMaxRight-i, p[2*localMaxCenter-i]) : 1;
            // 情况2，当i >= localMaxRight时，执行下述计算
            // 中心扩展法进行计算：
            // 1、赋初值为1
            // 2、当i位置的回文字子串两端(i-p[i]和i+p[i])处于[0, length)之间时
            // 3、并且r[i-p[i]]==r[i+p[i]]时
            // 4、对p[i]的值进行膨胀
            while (i - p[i] >= 0 && i + p[i] < r.length && r[i-p[i]] == r[i+p[i]])
                ++p[i];
            // i位置的回文子串长度计算完成后，重新审视局部环境变量和全局环境变量：

            // 局部环境变量
            // 如果i位置的回文子串右端坐标超过了localMaxRight
            // 那么就更新localMaxRight和localMaxCenter
            if (i + p[i] > localMaxRight) {
                localMaxRight = i + p[i];
                localMaxCenter = i;
            }
            
            // 全局环境变量
            // 如果i位置的回文子串长度超过了暂时全局最长的回文子串长度
            // 那么就更新暂时全局最长的回文子串长度和暂时全局最长的回文子串长度的中心位置
            if (p[i] > globalMaxLength) {
                globalMaxLength = p[i];
                globalMaxCenter = i;
            }
        }
        System.out.println(globalMaxLength - 1);
        // 终章
        // int globalMaxStart = (globalMaxCenter - (globalMaxLength - 1)) / 2;
        // System.out.println(line.substring(globalMaxStart, globalMaxStart + globalMaxLength - 1));  
    }
}