数据结构-manacher算法

第一种情况: 以t为中心，他的回文串为abedeks, 同时i’的回文为ede，那么i的回文也是ede。

第二种情况:以s为中心的回文串为 tabkdedk,而以i’为中心的回文串为abkde，已不再L和R之间。此时以i为中心的回文串就为kdedk.

第三种情况: 以t为中心的回文串为 ebcbestsebcbe, 以i’为中心的串为ebcbe, c和i’的正好在L边界重叠。此时以i为中心的回文串可以直接从R处开始向右边继续比较。

public class Code_Manacher {
    public static void main(String[] args) {
        String s = "66666";
        char[] str = manacherString(s);
        System.out.println(str);
        System.out.println(manacher(s));
    }

    public static int manacher(String s){
        if(s == null || s.length() == 0){
            return 0;
        }

        // 将字符串用#填充
        char[] str = manacherString(s);
        // 回文半径数组，使用该数组来加速
        int[] pArr = new int[str.length];
        int R = -1;
        int C = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2*C-i], R-i) : 1;

            while(i + pArr[i] < str.length && i-pArr[i] > -1){
                if( str[i+pArr[i]] == str[i-pArr[i]] ){
                    pArr[i]++;
                }else{
                    break;
                }
            }

            if(i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
            }

            max = Math.max(max,pArr[i]);
        }
        return max-1;
    }

    public static char[] manacherString(String str){

        char[] s = new char[str.length()*2+1];
        for (int i = 0; i <s.length; i++) {
            s[i] = (i%2 == 1 ? str.charAt(i/2) : '#');
        }
        return s;
    }

}