Manacher算法

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        char[] str = preprocessing(s.toCharArray());     // 预处理原始字符串，往每个字符之间加#
        int[] radius = new int[str.length];
        int R = -1, C = -1;       // 最远右边界(下一位置)及其对应的中心位置
        int max = 1;
        for(int i = 0; i < str.length; i++){
            radius[i] = i < R? Math.min(radius[2*C - i], R - i): 1;      // i在R内部或不在R内部的情况下，不需要检查的范围
            while(i + radius[i] < str.length && i - radius[i] >= 0){     // 没有越界
                if(str[i + radius[i]] == str[i - radius[i]]){
                    // 往外扩成功了半径就增加
                    radius[i] ++;
                }else{
                    break;
                }
            }
            // 最远右边界变大时要更新其位置和中心
            if(i + radius[i] > R){
                R = i + radius[i];
                C = i;
            }
            max = Math.max(max, radius[i]);
        }
        System.out.println(max - 1);
    }
    
    private static char[] preprocessing(char[] str) {
        StringBuilder sb = new StringBuilder();
        for(char c: str) sb.append("#").append(c);
        sb.append("#");
        return sb.toString().toCharArray();
    }
}