Manacher 算法求解最长回文子串的长度。虽然难但是可以有效降低时间复杂度。左神视频P13学习记录

public class Manacher {
    public static void main(String[] args) {
        String s ="c";
        int[] res = maxcpsLength(s);  //返回中心点和最大的回文半径
        int start  = res[0]-(res[1]-1)/2;  //中心点
        System.out.println(s.substring(start,start+res[1]));
    }
    /*
       R回文圈的最右边界
       Case1：   # 1 # 2 # 1 #...
              -1 0 1 2 3 4 5 6
              R=-1 中心点位置是0>R 在右边界中，直接暴力从中心点向两边暴力破解，R变大
       Case2： (# 1 # 2 # 2 # 1 #)...
               L   i'  C   i   R
           2-1: i'的回文区域在（L,R）内部中.i的回文半径就是i‘的半径
           abcdckskcdcba
           L i‘  c   i R   i’的回文区域在（L，R）中。i的回文半径和i‘一样    R不变
           2-2: abcdedcbakabcdedcft  i‘的回文区域超过了L
                  L i'   c    i   R
                  那么回文半径就是 i-R的距离                              R不变
           2-3: abcdcbakskabcdcba  i'的回文半径刚好在边界上
                   i’   c    i
                这种情况有可能R会增加，继续扩大，需要继续判断                R变大
     */
    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[] maxcpsLength(String s){
        char[] str = manacherString(s);
        int[] parr = new int[str.length];   //回文半径数组
        int C = -1;   //中心位置
        int R = -1;   //定义R是回文右边界的后一个位置，所以有效区间是R-1位置
        int max = Integer.MIN_VALUE;
        int[] res = new int[2];
        for(int i=0;i<str.length;i++){
            parr[i] = R>i? Math.min(parr[C*2-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表示对称区间到过哪里，一直扩大直到数组末尾
                R= i+parr[i];
                C = i;
            }  //求出数组的半径即可
            if(max<parr[i]){
                max = parr[i];  //这儿存的是半径的值
                res[0] = i;
                res[1] = max;
            }
        }
        res[1]=res[1]-1;  //对应原来的
        res[0]=(res[0]-1)/2;  //偶数位置现在是虚轴，所以-1除2，而奇数位置是实的-1无影响
        return res;
    }