Manacher（马拉车）算法

题目：

求一个给定字符串的最大回文长度（一个句子如果正着读与倒着读的意思一样,就可以称为"回文句）

思路：

暴力的解法：首先把字符先变成，manacherString（自定义），因为字符串的长度可以由奇数或者偶数，只有奇数才能有对称的扩法，所以得把字符串变成奇数长度且不影响结果，怎么做呢，在每个字符左右加相同的标识符，比如一个字符串"121",变成"#1#2#1#"。然后从第一个字符的位置开始向两边扩看看两边的是否相等，如果相等继续扩直到不相等，依次找，取找完的最大值
Manacher解法：第一步和暴力解法一样，把字符串变成manacherString，假设有以下变量，R最大回文半径的右边界下标，C当前最大回文半径的位置，L最大回文半径的左边界下标，i所求的位置，接下来如下图四种情况：

马拉车.png

代码：

    //把每个字符串不管是奇字符串还是偶字符串，都在字符左右加标识符（任意在这里用 # ）
    //比如 1 2 1  就变成 # 1 # 2 # 1 #  这样处理不管奇数偶数都变成偶数长度的数组
    public static char[] manacherString(String str){
        char[] charArr = str.toCharArray();
        char[] res = new char[2*str.length()+1];
        int index = 0;
        for (int i =0;i<res.length;i++){
            res[i] = (i&1)==0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static int maxLcpsLength(String str){
        if (str==null||str.length()<1){
            return 0;
        }

        char[] charArr = manacherString(str);
        //存储i位置的最大回文半径
        int[] pArr = new int[charArr.length];
        int max = Integer.MIN_VALUE;
        int r = -1;
        int c = -1;
        for (int i = 0;i<charArr.length;i++){
            //把四种情况用一个判断条件写出来，给i位置的回文半径赋一个初始值
            pArr[i] = r>i ? Math.min(r-i,pArr[2*c-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]>r){
                r = i + pArr[i];
                c = i;
            }
            max = Math.max(max,pArr[i]);
        }
        //因为最开始回文半径赋值为1，所以多了1 得减去
       return max-1;
    }

扩展：

问题：给定一个字符串str1，只能往str1的后面添加字符变成str2，要求str2
整体都是回文串且最短。

思路：

1.只要求出包含了str1中最后一个字符的最长回文子串s即可。

2.然后将子串s在str1中之前的字符逆序添加到str1末尾即可。

如“abc12321”，包含“1”的最长回文子串是“12321”，将“abc”逆序添加到“abc12321”末尾，变成“abc12321cba”，即为所求的str2。

代码：

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 String shortestEnd(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];
        int index = -1;
        int pR = -1;
        int maxContainsEnd = -1;
        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;
            }
        }
        char[] res = new char[str.length() - maxContainsEnd + 1];
        for (int i = 0; i < res.length; i++) {
            res[res.length - 1 - i] = charArr[i * 2 + 1];
        }
        return String.valueOf(res);
    }