Manacher算法简单应用

题目： 给定一个字符串str1, 只能往str1的后面添加字符变成str2, 要求str2整体都是回文串且最短。
举例：str1 = "ABC12321", 则str2 = "ABC12321CBA"

分析：
    由于str2整体是一个回文串，因此如果str2=str1+others，必然是回文串。显然，最坏情况下，另一部分刚好是str1的倒序。要使得str2最短，就得想办法将str1的后半部分last去掉，再将剩余的部分逆序，就可以得到others。如果last可以去掉，则last本身必然是回文串。而在str2最短的限制条件下，只能使得last最长。因此，问题就变成了求包含str1最后一个字符的最长的回文串的问题。
    既然是求回文串，那么时间复杂度为O(n)的manacher算法自然是一个很好的选择。
    直接上代码：

public class Main {
    public static void main(String[] args) {
        String s = "ABC12321";
        System.out.println(s + new StringBuilder(s.substring(0, s.length() - plalindrome(s))).reverse().toString());
    }

    public static int plalindrome(String str) { // 获取包含字符串最后一个字母的回文串的最大长度
        char[] cArr = manacherString(str);
        int cur = -1, r = -1, max = Integer.MIN_VALUE;
        int[] p = new int[cArr.length];
        for (int i = 0; i != cArr.length; i++) {
            p[i] = r > i ? Math.min(p[2 * cur - i], r - i) : 1;
            while (r + p[i] < p.length && i - p[i] > -1) {
                if (cArr[i + p[i]] == cArr[i - p[i]]) {
                    p[i]++;
                } else {
                    break;
                }
            }
            if (r + p[i] == p.length) { //p.length - 1为原始字符串的最后一个位置
                max = Math.max(max, p[i]);
            }
            if (i + p[i] > r) {
                r = i + p[i];
                cur = i;
            }
        }

        return max - 1;
    }

    public static char[] manacherString(String str) {
        if (str == null) {
            return null;
        }
        char[] cArr = new char[2 * str.length() + 1];
        int index = 0;
        for (int i = 0; i < cArr.length; i++) {
            cArr[i] = (i & 1) == 1 ? str.charAt(index++) : '#';
        }
        return cArr;
    }
}