Manacher算法-解最长回文子串

回文问题

LeetCode-5-最长回文子串

回文问题是一个常见的算法问题，我们在刷题的时候经常看见看见此类问题，一般常见的解法是暴力解法，

暴力解法1.0

• 暴力解法的方法就是将字符串拆分开来然后逐个进行判断是否为回文字符串，但是这种解法还是有一个很大的bug，当是奇数的时候，就会造成并不能计算到最长的回文字符串。

所以需要对这种暴力的解法做一个优化，对其进行优化 2.0

• 将字符串进行改变，在每个字符串的左右都加上一个特殊字符（随便什么字符都行），然后再进行逐个查找回文字符串，这样就能保证查到的回文字符串一定是最大的。但是这样优化后的暴力解法的时间复杂度还是堪忧，为O(N^2)。

Manacher算法中的基础概念

• 回文直径
• 回文半径

image-20210518121123707

1、回文半径数组radius

回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度

每个位置的回文半径组成的数组就是回文数组，所以#a#c#b#b#c#b#d#s#的回文半径数组为[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]。

img

2、最右回文右边界R

一个位置最右回文右边界指的是这个位置及之前的位置的回文子串，所到达的最右边的地方

image-20210518121554906

• 第一步

image-20210518122057744

• 第二步

image-20210518122629010

3、最右回文右边界的对称中心C

就是上面提到的最右回文右边界的中心点C 如下图，p=4时，R=8，C=4

image-20210518123153162

三、Manacher算法的流程

首先大的方面分为两种情况：

第一种情况：下一个要移动的位置在最右回文右边界R的右边。

image-20210518124135552

在这种情况下，采用普遍的解法，将移动的位置为对称中心，向两边扩，同时更新回文半径数组，最右回文右边界R和最右回文右边界的对称中心C。

第二种情况：下一个要移动的位置在最右回文右边界R或是在R的左边(i<=R)

image-20210518124942384

image-20210518125823256

1、下一个要移动的位置i在最右回文右边界R的左边(i<=R),对称点PI的回文半径在[L,R]内

image-20210518131510109

2、下一个要移动的位置i在最右回文右边界R的左边(i<=R) 切对称点pi的radius[pi]回文半径在[L,R]之外

image-20210518132439367

radius[i]=R-i+1

image-20210518134035511

3、下一个要移动的位置I不在最右回文右边界R的右边，L压线的情况

image-20210518134949869

这种情况下i的回文半径就还要继续往外扩，但是只需要从R之后往外扩就可以了，扩了之后更新R和C。

image-20210518135432064

四、Manacher时间复杂度分析

从上面的分析中，可以看出，第二种情况的1，2的求某个位置的回文半径的时间复杂度是O(1)，对于第一种情况和第二种情况的3，R是不断的向外扩的，不会往回退，而且寻找回文半径时，R之内的位置是不是进行判断的，所以对整个字符串而且，R的移动是从字符串的起点移动到终点，时间复杂度是O(n),所以整个manacher的时间复杂度是O(n)。

image-20210518140232899

五、Manacher的代码实现

public static int manacherDetail(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[]中的元素初始化都为1，如果当i点处于目前最大回文字符串的右边界R内部时，则取以最大回文字符串的中心点C找他在parr数组的对称点
            //如果改对称点的回文区域范围已经有在最大回文字符串的区域范围外面时，就取二者的最小值
            parr[i] = R>i ?Math.min(parr[2*C-i],R-i):1;
            //在每个parr元素已有的范围内去判断以外的范围是否还能不能构成回文串，如果可以，则回文半径要加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赋值为最大的回文半径
            max = Math.max(max, parr[i]);
        }
        //最后返回的数由于有特殊字符的加入，需要减去1
        return max - 1;
    }

    //加特殊#字符串
    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;
    }

LeetCode-5-最长回文子串

class Solution {
    public static String longestPalindrome(String str) {
        if (str == null || str.length() == 0) {
            return "";
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];
        int index = -1;
        int pR = -1;
        int max = Integer.MIN_VALUE;
        int mid = 0;
        for (int i = 0; i != charArr.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
            if (max < pArr[i]) {
                max = pArr[i];
                mid = i;
            }
        }
        mid = (mid - 1) / 2;
        max = max - 1;
        return str.substring((max & 1) == 0 ? mid - (max / 2) + 1 : mid - (max / 2), mid + (max / 2) + 1);
    }

    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;
    }
}

image-20210518151526803