ac

[举例]
str = abcd123321，在必须包含最后一个字符的情况下，最长的回文子串是 123321，之前不是最长回文子串的部分是 abcd，所以末尾应该添加的部分就是 dcba。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    /**
     * https://blog.csdn.net/qq_26437925/article/details/52181738
     */
    public static void main(String[] args) throws Exception {
        String s = reader.readLine();
        char[] ch = s.toCharArray();
        char[] arr = new char[2 * ch.length + 1];
        int len = arr.length;
        int chi = 0;
        for(int i = 0; i < len; i++){
            arr[i] = (1&i) == 0 ?'#' : ch[chi++];
        }
        //  p[i] 表示 以i位置为中心的回文半径长（其长度减去1，表示在原字符串中以i为中心的回文长度）
        int[] p = new int[len];
        // 表示 回文半径最长的位置的下一个位置（pR总是比上一个pR值要大的）
        int pR;
        // 表示 回文中心点，pR更新时index要跟着更新，否则index不用更新
        int index;

        // index = 0 的情况
        p[0] = 1;
        index = 0;
        pR = 1;
        // index = 1 的情况
        p[1] = 2;
        index =1;
        pR = 3;

        int includeEndIndex = -1; // 如果回文包含到最后一个字符了可以结束了
        for(int i = 2;i<len;i++){
            int _i = index - (i - index);   //i的对称位置i'
            int index_left = index - p[index] + 1;  // index的左大
            int index_right = pR - 1;    // index的右大
            int _i_left = _i - p[_i] + 1;    //i的对称位置i'的左大

            if (_i < index_left) {
                int j = i + 1;
                int _j = i - 1;
                while (_j >= 0 && j < len && arr[_j] == arr[j])
                {
                    _j--;
                    j++;
                    if (_j < 0 || j >= len) {
                        break;
                    }
                }
                p[i] = j - i;
                pR = j; // 更新pR 和 index
                index = i;
            }else{
                if(_i_left < index_left){
                    p[i] = index_right - i + 1;
                }else if(index_left < _i_left){
                    p[i] = p[_i];
                }else {
                    // 往外扩
                    int j = pR;
                    int _j = i - (pR - i);
                    while ( _j >= 0 &&  j < len && arr[_j] == arr[j])
                    {
                        _j--;
                        j++;
                        if (_j < 0 || j >= len) {
                            break;
                        }
                    }
                    p[i] = j - i;
                    pR = j; // 更新pR 和 index
                    index = i;
                }
            }
            // 扩展到的位置已经包含了最后一个字符了
            if(pR == len){
                includeEndIndex = p[i];
                break;
            }
        }
        char[] res = new char[ch.length - (includeEndIndex - 1)];
        for(int i=0;i<res.length;i++){
            res[res.length - i - 1] = ch[i];
        }
        System.out.println(String.valueOf(res));
    }

}
/*
abcd123321
dcba

ababab
a
 */