Manacher算法解决最长回文子串问题-Java版

绝地灬酷狼 2022-02-01 16:25 219阅读 0赞

# Manacher算法解决最长回文子串问题 #

最长回文子串问题，就是给定一个字符串，求出字符串中最长回文子串的长度。回文串就是从头到尾遍历和从尾到头遍历是一模一样的。  
暴力求解，把字符串所有子串都找出来，再挨个判断是否为回文子串，再记录最长的长度，这个方法当然是可以的，但是复杂度太高！不推荐！  
所以设计了**Manacher算法(马拉车算法)用来解决最长回文子串问题**！

## 字符串初始化处理 ##

奇数长和偶数长的回文子串的字符中心是不一样的，不好判断，为了解决这个问题，**Manacher算法将所有字符串的长度都变成奇数**，方法就是**在原字符串的相邻字符之间加分隔符（比如说\#）**，例如ababc，变成\#a\#b\#a\#b\#c\#；abab，变成\#a\#b\#a\#b\#。所有字符串长度都是奇数，还不影响回文性。

## 回文半径存储数组的定义 ##

Manacher算法还建立了一个辅助数组，用来**存储以str\[i\]为中心的回文字符串的回文半径的长度**。例如回文字符串：\#a\#b\#a\#b\#a\#，以第三个a为中心，即str\[5\]为中心，这个回文字符串的长度为11，而回文半径是回文字符串长度的一半，即(11+1)/2=6，（要包括回文中心字符），所以len\[5\]=6。  
**这里要注意一点的是：调整后加入\#的字符串str，以str\[i\]为中心的回文字符串的长度为2×len\[i\]-1，而其中有len\[i\]个分隔符\#，所以原字符串的长度为len\[i\]-1。也就是说最后只要输出len中最大的数字-1就是最长回文子串的长度。**

## 回文半径存储数组的计算 ##

**Manacher算法的精髓就是只需要从头到尾遍历str一次！！！**

如何实现呢？我们需要设置**两个标志位**，**centre和right**，**centre是当前回文子串的中心点，right是当前回文子串的右边界(right并不包含在回文子串中！)**。一开始初始化，centre=right=-1。**当i从0遍历到str.length-1时，需要动态的改变centre和right值**，就可以计算出以str\[i\]为中心的回文半径存入len数组中。

**这里需要注意的是，i一定>=centre，有了i的推进，centre和right才会更新。**

什么时候要改变centre和right值呢，有**两大情况**：

1.  **当i值在right的左边：即 centre<=i<right**，如下图  
    ![图][20190514220430356.png]  
    图中 **l 是 以cen为中心的回文子串的左边界，j 为 i 以 cen 为中心的对称点**。我们要时刻注意到**回文特性**，**即 `str[l+1...cen-1]` 与 `str[r-1...cen+1]`是相同的**，所以**以 i 为中心的回文子串有可能与以 j 为中心的回文子串是一样的**，至少有一部分是相同的。
    
    接下来，这里根据 **以 j 为中心的回文子串的长度不同**，会再细分成**两种情况**：  
    （1）**以 j 为中心的回文子串很短**，如下图  
    ![图][20190515011944238.png]  
    这种情况下，**len\[i\]至少跟len\[j\]一样大**，为什么至少一样大，什么时候len\[i\]比len\[j\]大呢，以上图为例，**以 i 为中心的回文子串的右边界还可以向右扩展，这扩展的部分在 j 是无法匹配的**。所以可以**先将len\[i\]保存为len\[j\]，再以i为中心左右两边扩展。**
    
    （2）**以 j 为中心的回文子串很长**，如下图  
    ![图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]  
    以 j 为中心的回文子串很长，可以看出左边界已经超过了 l ，但是以 i 为中心的回文字符长度，如果只按照回文性来判断，**len\[i\]的值现在只能确定为 r-i** ，len\[i\]<len\[j\]，因为如图中红色单元格所示，这些单元格是否满足回文还需要进一步判断，**所以 `len[i] = r-i`，再以i为中心左右两边扩展**。
    
    **上面两个情况合并一下，即当i值在right的左边时，因为不知道当前j符合哪一种情况，所以 `len=Math.min(len[2*cen-i], right-i)`，取两个中间的最小值即可。**
2.  **当i值在right的右边：即 i>=right**  
    ![图][20190515001241611.png]  
    说明以 i 为中心的回文子串还没有被访问过，所以**当前len\[i\]的长度为1，即为i本身，再以i为中心左右两边扩展**。

## Manacher算法-Java版 ##

// 处理字符串
    public static char[] manacherString(String str){
        char[] chars = str.toCharArray();
        char[] res = new char[chars.length*2+1];
        int index = 0;
        for(int i=0;i<res.length;i++)
            // 偶数位加 # ，奇数位不变
            res[i] = (i&1)==0?'#':chars[index++];
        return res;
    }
    
    // 马拉车算法
    public static int maxLcpsLength(String str){
        char[] chars = manacherString(str);
        int[] len = new int[chars.length]; // 记录每个回文字符串的长度
        int right = -1; // 当前回文的右边界
        int cen = -1; // 当前回文的中心
        int max = -1; // 记录回文的最大值
        for(int i=0;i<chars.length;i++){
        
            // 2*cen-i是i点关于cen的对称点
            // right>i时，Math.min(len[2*cen-i], right-i)，两种情况取最小，往外扩
            // right<=i时，以i为中心的回文没有被访问过，所以当前回文字符串只有i，len[i]=1
            len[i] = right>i? Math.min(len[2*cen-i], right-i) : 1;
            
            // 以i为中心，左右扩
            while(i-len[i]>-1 && i+len[i]<chars.length){
                if(chars[i-len[i]]==chars[i+len[i]])
                    len[i]++; // 左右字符相等，符合回文，len++；
                else
                    break;
            }
            // 更新当前回文的右边界以及中心
            if(i+len[i]>right){
                right = i + len[i];
                cen = i;
            }
            max = Math.max(max, len[i]);
        }
        return max-1;
    }

[20190514220430356.png]: /images/20220201/9f78faf9cb7348af91e240e4f1d359b7.png
[20190515011944238.png]: /images/20220201/0eec4947ee65457faa8012e6295b8368.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]: /images/20220201/038feb189fb04bb98c0202dd9e65c127.png
[20190515001241611.png]: /images/20220201/f93a8b3bab6e48aa822568dae30d9b73.png