经典解法：在数的两边加虚数，即可以找到奇数回文，也可以找到偶数回文。时间复杂度O(N^2)
    Manacher：回文直径半径 ，回文半径数组，之前扩的最长的右边界 R，最长右边界的中心点C。
    1）当来到某个中心点i，这个点没有在最长的右边界里，暴力扩，没有任何优化。
    2）当来到某个中心点i，这个点在最长的回文右边界里，
    那么必有 L i’ C i R
    第一种情况：i’回文区域彻底在L到R的内部，i的回文半径一定和i’一样，不可能多。
    L x i’ y c z i l R ； x!=y y==z x==l z!=l 不可能多。
    第二种情况：i’回文区域跑到L的外面去了。i的回文半径是R’到R。
    L i’ C R’ i R
    xL i’ L’y c zR’ i Rp x==y y==z x!=p z!=p，不可能多
    第三种情况：i’回文区域正好和L压线。
    i’ c i** ,是与之相对应的，但不确定是否会多，需要去验。

    2.     public static int manacher(String s) {
    3.         if (s == null || s.length() == 0) {
    4.             return 0;
    5.         }
    6.         // "12132" -> "#1#2#1#3#2#"，加特殊字符
    7.         char[] str = manacherString(s);
    8.         // 回文半径数组
    9.         int[] pArr = new int[str.length];
    10.         int C = -1;
    11.         // 讲述中：R代表最右的扩成功的位置
    12.         // coding：最右的扩成功位置的，再下一个位置,
    13.         // 最右扩成功的位置是R-1
    14.         int R = -1;
    15.         int max = Integer.MIN_VALUE;// 扩出来最大值
    16.         for (int i = 0; i < str.length; i++) { // 0 1 2
    17.             // R第一个违规的位置，i>= R
    18.             // i位置扩出来的答案，i位置扩的区域，至少是多大。
    19.             // R>i i在R内， 2 * C - i就是i',包含了三种情况
    20.             // R<i 不用验的位置1，自己不用验证自己
    21.             // 回文半径数组不仅能解决最长回文，还能解决其他的，是最重要的
    22.             pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
    24.             // 至少不用验的区域得到后，看能不能扩大，虽然只有两种情况往外扩，但这样代码少，而且不用扩的情况，扩一次就会失败
    25.             // 不越界并且左边界也不能越界
    26.             while (i + pArr[i] < str.length && i - pArr[i] > -1) {
    27.                 if (str[i + pArr[i]] == str[i - pArr[i]])
    28.                     pArr[i]++;
    29.                 else {
    30.                     break;
    31.                 }
    32.             }
    34.             // 如果更往右了更新R更新C
    35.             if (i + pArr[i] > R) {
    36.                 R = i + pArr[i];
    37.                 C = i;
    38.             }
    39.             max = Math.max(max, pArr[i]);
    40.         }
    41.         return max - 1;
    42.     }