得到的最短的回文长度

1.题目描述

京京和东东是好朋友。东东很喜欢回文。回文是指从前往后读和从后往前读是一样的词语。京京准备给东东一个惊喜，先取定一个字符串s，然后在后面附上0个或者更多个字母形成回文，京京希望这个回文越短越好。请帮助京京计算他能够得到的最短的回文长度。

输入描述：

输入包括一个字符串s，字符串s长度length(1 ≤ length ≤ 50)。

输出描述：

输出一个整数，表示京京能够得到的最短的回文长度。

示例：

输入

abab

输出

5

2.解题思路

转化成求字符串中的最长回文子串的大小，结果即不是回文那部分逆序即可。

从左往右，

三个概念：回文半径数组pArr[]，回文右边界pr，取得回文右边界的轴中心i

1）没在回文右边界里边，暴力

2）i’在回文范围里，回文右边界不扩

3）i’在回文范围外，回文右边界不扩

4）i’压线，回文右边界扩

直到回文右边界第一次到达最后一个字符

3.代码

import java.util.*;
public class Main {
    //manacher预处理
    public static  char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static  int shortestEnd(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];
        int index = 0;

        int pR = 0;

        int maxContainsEnd = 0;

        for (int i = 0; i != charArr.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
            //右边界到达最后一个字符就结束，那个中心就是包含最后一个字符的最长的回文

            if (pR == charArr.length) {
                //得到那个中心

                maxContainsEnd = pArr[i];
                break;
            }
        }
        //原来的长度 + 扩充的长度（字符最大的半径[str.length+1-回文最大的半径maxContainEnd]）

        return str.length() + str.length() - maxContainsEnd + 1;
    }

    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        String s = sr.nextLine();
        System.out.println(shortestEnd(s));      

    }

}