关于字符串回文的Manacher算法

对于Manacher算法自己研究了一会，总算是理解了其中的含义，乘着有时间正好可以过来记录下：

思路：

1. 将字符串变成奇数，通过加非字符串里面的符号表示，不过一般都是加的#
2. 找出以当前索引为中点的最长回文数长度，并且记录，例如：#a#b#a,这个字符串所对应的长度便是[1,2,1,2,1,1],因为在#的时候组成不了回文，所以#这里是1，而到了a这里，因为#a#组成了回文，所以a的最长回文字符串长度是2,以此类推
3. for循环开始比较，在这里一般来讲是首先需要定义一个字符串的边界变量，以防止数组越界，另外一个就是最长回文字符串的中点坐标，以此类推就可以

代码：

将填充符号计入到需要匹配的的字符串中

//最大回文串的数组
        StringBuilder sb =new StringBuilder();
        sb.append("#");
        for(int i=0 ;i<str.length() ;i++){
            sb.append(str.charAt(i));
            sb.append("#");
        }
        String s1 =sb.toString();

然后再定义一个最大的字符串长度和一个最长回文字符串的中点位置的坐标

int array=[s1.length()];
int maxRight =0;
int mid =0;
for(int i =0 ;i<s1.length() ;i++){
    int r=1; //定义最小的半径
    if(i> maxRight){
        r=Math.min(array[2*mid -i ],maxRight-i);
    }
    //以此为中心点继续扩张
    while(i - r > >0 && i+r <s1.length() && s1.charAt(i-r) == s1.charAt(i+r) ){
        r++;
    }
    //在这里需要减一的原因是因为需要将当前的多加一去除掉，因为i算了一遍当前的索引,r又算了一遍当前的索引
    if(i+r -1 <right){
        right =i +r -1;
        mid =i;
    }
    array[i]=r;
}


//或者可以将for循环修改为如下：
for (int i = 0; i < s1.length(); i++) {
        int r = 0;
        if (array[mid] + mid > i) {
            r = Math.min(array[2 * mid - i], array[mid] + mid - i);
        } else {
            r = 1;
        }

        while (i - r > 0 && i + r < s1.length() && s1.charAt(i - r) == s1.charAt(r + i)) {
            ++r;
        }
        if (mid + array[mid] < array[i] + r) {
            mid = i;
        }
        if (r > maxLength) {
            maxLength = r;
        }
//            if(i+r -1 >maxLength){
//                maxLength =i+r-1;
//                mid=i;
//            }
//            array[i] = r;
    }

简单一点的代码如下：

for(int i =0 ;i<s1.length() ;i++){
   r=Math.min(array[2*mid -i],right -i):1;
   //这种情况考虑的是当前索引位置再最长回文字符串之间，而且这个索引说不定还有更长的回文字符串，所以在这里需要一个while判断
   while(array[i-array[i]] == array[i+array[i]]) ++r; 
   if( i +array[i] >right){
       right =i+array[i];
       array[i]=r;
   }
}

在上面的代码中为什么是非要array[i-array[i]] == array[i+array[i]]相等才会进行半径的增加呢？这里其实有几种情况需要考虑的