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();
    }
}

#include<cstdio>
(802)#include<cstring>
bool ishuiwen(char str[],int l,int r){
    int k=0;
    for(int i=l;i<=(l+r)/2;++i){
        if(str[i]!=str[r-k])
            return false;
        ++k;
    }
    return true;
}
int main(){
    char str[500010];
    while(scanf("%s",str)!=EOF){
        int len=strlen(str);
        int i;
        for(i=0;i<len;++i){
            if(ishuiwen(str,i,len-1))
                break;
        }
        for(i=i-1;i>=0;--i){
        	printf("%c",str[i]);
        }
    }
    return 0;
}