Manachar算法(马拉车算法)：快速求取最长回文子串

Love The Way You Lie 2023-09-30 09:18 10阅读 0赞

当我们求取最长回文子串时，常见的方法就是中心扩散法，即从字符中心出发，向两边对比，检查是否相等，若等于，则继续检查，并使当前字符中心对应的最长回文子串长度加一，否则，结束该字符中心的回文检查，比较与当前整个字符串的最长回文子串，考虑是否更新整个字符串的最长回文子串长度，继续进行下一个字符的判断。

这种方法的时间复杂度仍为  O ( n 2 ) O(n^2) O(n2) ，较普通的暴力破解的方法有着不错的优化，但也不是最佳的思路，相关的代码如下：

public class Solution {
        
        private int max = 0;
        private String res = "";
        public String longestPalindrome(String s) {
        
            if (s.length() == 1) {
         return s; }
            for (int i = 0; i < s.length()-1; i++) {
        
                checkPalindromeExpand(s,i,i);
                checkPalindromeExpand(s,i,i+1);
            }
            return res;
        }
        public void checkPalindromeExpand(String s, int low, int high) {
        
            while (low >= 0 && high < s.length()) {
        
                if (s.charAt(low) == s.charAt(high)) {
        
                    if (high - low + 1 > max) {
        
                        max = high - low + 1;
                        res = s.substring(low,high+1);
                    }
                    low--; high++;
                } else {
        
                    return;
                }
            }
        }
    }

当然，上面这种算法也有优化的空间，基本的思路如下：

*  统计字符出现频率，用数组表示出现频率，当某个字符出现频率为 1 时，认为该字符可能为某段回文子串的中心点，否则，就不属于任何一个回文子串
 *  找出频度为1的字符a，看以a为单核中心向外扩散，求最长回文；如果没有回文，就将它从串中断开，进行分治；如果回文长度超过记录，就保存它
 *  然后从左到右查回文，只有长度超过记录，才保存
 *  第一次串分割完毕后，进行分治，重新统计频度，回到1步骤

实现代码可以借鉴：[小马哥最长回文子串长度求取][Link 1]

### Manachar算法 ###

求取最长回文子串的长度的最佳方法为 Manachar算法 ，俗称马拉车算法。在了解这个算法之前，我们必须先理解回文子串的一些性质：

*  假设对于一个回文串，以及其中心位置，由回文串的性质可知，从其中心向两侧逐步扩散到边界为止，每一步所对应范围的字串都是回文串
 *  如果我们已知一个回文串的中心点 mid 与其边界范围。那么，在大多数情况下，位于边界内且关于此中心点对称的两点a、b，如果有回文串以 a 为中心，那么以 b 为中心的回文串与以 a 为中心的回文串完全相同。并且，它们之间存在这样的关系： b = 2 × m i d − a b = 2 \\times mid - a b=2×mid−a
 *  回文串末尾位置到回文串中心位置的字符长度为该回文串的半径，若末尾位置的下标为 a ，中心位置的下标为 id ，回文串长度半径为 len ，即半径为 len 则它们存在如下关系：  
     a = i d + l e n ÷ 2 a = id + len\\div2 a=id\+len÷2  
    头尾添加一个非 \* 的特殊符号保证不越界，避免多次判断是否越界。

为方便处理，将字符串长度可能为奇数，可能为偶数的两种情况进行合并，即在每个字符的左右都加上一个特殊字符，比如 “ ∗ \* ∗”。防止越界情况的出现，在开头添加一个 “@”可看如下实践：

![马拉车算法图解三][ab4f6f47799645d1d11d0851ec7a1477.png]

从以上实践可得出，由于插入的 \# 号的个数必定等于字符个数加一再加上 两个@ 字符，所以总长度是偶数+奇数=奇数，通过这种方法，可以将字符串的长度都化为奇数，这样就不需要对长度奇偶性进行分情况讨论。

对字符串完成预处理之后，定义一个数组 len 存入字符串的每个字符作为回文串中心扩散的回文子串长度且为去掉特殊字符的原字符串的总长。

![马拉车算法图解一][99a9856a30988da11741ba979c387f9f.png]  
 最长回文子串长度： l e n \[ i \] − 1 最长回文子串长度：len\[i\]-1 最长回文子串长度：len\[i\]−1  
证明方法如下：

1.  转换后，所有回文子串的长度为奇数，故以中心位置下标为 i 的最长回文串长度为  2 × l e n \[ i \] − 1 2 \\times len\[i\] - 1 2×len\[i\]−1
2.  在回文串中，特殊字符数为 len\[i\] ，而除去特殊字符数剩下的就为原字符数，即  ( 2 × l e n \[ i \] − 1 ) − l e n \[ i \] = l e n \[ i \] − 1 (2\\times len\[i\]-1)- len\[i\] = len\[i\] -1 (2×len\[i\]−1)−len\[i\]=len\[i\]−1

问题就转换为了求取 len\[i\] 中所有的数。

已知 P 的最长回文子串长度 len\[p\]，则回文串左边界为 p - len\[p\]，右边界为 p + len\[p\]

假设在已知中心 p 的左边有一点 j ，其对称点为 i，

*  若 i > len\[p\] + p ，暴力比较 ,通常出现在求取最开始时。
 *  若 i < len\[p\] + p ,且 len\[j\] < len\[p\] + p - i (右边界到 i 的距离)，则他被完全包裹入以 p 为中心的子串中，必有 len\[i\] = len\[j\]
 *  若 i = len\[p\] + p ,且 len\[j\] >= len\[p\] + p - i ， len\[i\] = len\[j\]，此时，可能存在超出原有 p 的回文区域，仍需从边界 i + 1 + len\[i\] 出发一一比较

![马拉车算法图解二][b2a2d6ba2b1887e39e037a209a57c319.png]

做完当前中心 i 的长度求取之后，判断是否 i 的回文区域右边界大于原有回文右边界值，若大于，更新中心点为 i ，右边界为 i 的回文右边界。

解决 len 数组的求取问题就基本完成对于 Manachar 算法的理解。相关代码如下：

import java.util.Scanner;
    
    public class Manacher {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            String str = in.next();
            String res = longestPalindrome(str);
            System.out.println(res + ": " + res.length());
        }
    	//插入字符
        public static String preProcess(String s) {
        
            int n = s.length();
            if (n == 0) {
        
                return "^$";
            }
            String ret = "^";
            for (int i = 0; i < n; i++)
                ret = ret + "#" + s.charAt(i);
            ret = ret + "#$";
            return ret;
        }
        // 马拉车算法
        public static String longestPalindrome(String str) {
        
            String S = preProcess(str);
            int n = S.length();// 保留回文串的长度
            int[] len = new int[n];
            int center = 0, right = 0;// 保留边界最右的回文核心以及右边界
            // 从第 1 个字符开始
            for (int i = 1; i < n - 1; i++) {
        
                // 找出i对于后面核心的对称
                int mirror = 2 * center - i;
                if (right > i) {
        
                    // i 在右边界的范畴内，看看i的对称点的回文串长度，以及i到右边界的长度，取两个较小的那个
                    // 不能溢出之前的边界，否则就得核心拓展
                    len[i] = Math.min(right - i, len[mirror]);
                } else {
        
                    // 超过范畴了，核心拓展
                    len[i] = 0;
                }
    
                // 核心拓展
                while (S.charAt(i + 1 + len[i]) == S.charAt(i - 1 - len[i])) {
        
                    len[i]++;
                }
    
                // 看看新的索引是不是比之前保留的最右边界的回文串还要靠右
                if (i + len[i] > right) {
        
                    // 更新核心
                    center = i;
                    // 更新右边界
                    right = i + len[i];
                }
    
            }
    
            // 通过回文长度数组找出最长的回文串
            int maxLen = 0;
            int centerIndex = 0;
            for (int i = 1; i < n - 1; i++) {
        
                if (len[i] > maxLen) {
        
                    maxLen = len[i];
                    centerIndex = i;
                }
            }
            int start = (centerIndex - maxLen) / 2;
            return str.substring(start, start + maxLen);
        }
    }

![求点赞转发][format_png]

[Link 1]: https://github.com/githubwoniu/learnprogram/blob/master/leetcode/05/note_bajdcc.md
[ab4f6f47799645d1d11d0851ec7a1477.png]: https://img-blog.csdnimg.cn/img_convert/ab4f6f47799645d1d11d0851ec7a1477.png
[99a9856a30988da11741ba979c387f9f.png]: https://img-blog.csdnimg.cn/img_convert/99a9856a30988da11741ba979c387f9f.png
[b2a2d6ba2b1887e39e037a209a57c319.png]: https://img-blog.csdnimg.cn/img_convert/b2a2d6ba2b1887e39e037a209a57c319.png
[format_png]: https://img-blog.csdnimg.cn/img_convert/35ee50d2cac7305d2356e2bf37f47998.webp?x-oss-process=image/format,png