马拉车算法

马拉车算法用于求解最长回文子串。
说明两个概念：
R：回文串的半径。
C：回文中心。
步骤一：处理字符串，将其字符间添加特殊字符#，用来消除奇偶的差异。

 public static  char[] change(String s){
        char[] chars = new char[s.length()*2+1];
        int i=0;
        int index=0;
        while(i<chars.length){
            chars[i++]='#';
            chars[i++]=s.charAt(index++);
        }
        return chars;
    }

image.png

 public static  int manacher(String s){
        char[] chars =change(s);
        int[] size= new int[chars.length];
        int R=-1;
        int C=-1;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<chars.length;i++){
            size[i]=R>i?Math.min(size[2*C-i],R-i):1;//判断是否超出边界R
            while(i+size[i]<chars.length&&i-size[i]>=0&&chars[i+size[i]]==chars[i-size[i]]){
                size[i]++;
            }//暴力求解
            if(size[i]+i>R){
                C=i;
                R=size[i]+i;
            }//更新R和C
            max=Math.max(max,size[i]);//更新最大值
        }
        return max;
    }