Manacher算法进阶问题

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
 
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 C = -1;
        int R = -1;
        int[] pArr = new int[str.length];
        for(int i=0; i<str.length; i++){
            pArr[i] = i<R ? Math.min(pArr[2*C-i],R-i) : 1;
            while(i+pArr[i]<str.length && i-pArr[i]>-1){
                if(str[i-pArr[i]]==str[i+pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if(i+pArr[i]>R){
                R=i+pArr[i];
                C = i;
            }
        }
        int index= C-pArr[C];
        StringBuilder sb = new StringBuilder();
        while(index>=0){
            sb.append(str[index]=='#' ? "" : str[index]);
            index--;
        }
        System.out.println(sb.toString());
    }
     
    private static char[] preprocessing(char[] str) {
        StringBuilder sb = new StringBuilder();
        for(char c: str) sb.append("#").append(c);
        sb.append("#");
        return sb.toString().toCharArray();
    }
}