【搞定算法】Manacher 马拉车算法

朴灿烈づ我的快乐病毒、 2021-12-17 00:33 331阅读 0赞

求一个字符串中的最长回文子串，这是一道经典的面试题目，解法有很多，详细可见：最长回文子串问题。其实个人感觉 Manacher 算法代码实现还是有一定难度的，真正在做题目的时候采用的可能性不是很大，但是由于 Manacher 算法求解回文子串方面的时间复杂度为 O(N)，所以了解其思想还是很有必要的，coding 能力比较强的话，采用 Manacher 算法解决最长回文子串问题更是最合适不过了。

> **回文串**的概念：一个字符串正着读和倒着读都是一样的，比如：abba、noon 等；
> 
> **最长回文子串**：一个字符串的最长回文子串即为这个字符串的子串中，是回文串的最长的那个。

##  1、暴力解法 ##

思路：对字符串遍历每一个字符，以对每一个字符，以它为中心，往两边扩，找出以该字符串为中心的回文串大小。这里要分为两种情况，一种是回文串长度是奇数的情况，另一种是回文串长度是偶数的情况，奇数直接扩能找出回文，偶数则不可以。为了解决这样的奇偶差异，可以在每个数字的前后加上一个虚轴 “\#”。

## 2、Manacher 解法 ##

> 思路：和暴力解法一样，都是每一个字符往两边扩，只是利用前面的结果加速了这个过程，对每个字符，都从它至少的**回文半径**大小开始往两边扩。

*  **相关技巧前提：**

1、首先，Manacher 算法提供了一种巧妙地办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑，具体做法是，**在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，一般情况下可以用\#号，新字符串长度为原本的 2 倍 + 1**。下面举一个例子：

![20190706175325560.png][]

2、**回文半径数组 pArr**：记录每个位置往两边扩，能扩出来的回文半径大小【后面的就能利用前面的进行加速】；

3、**R**：所有回文半径中最靠右的位置【所有回文右边界中最大的一个】【每个字符往两边扩下，最右到了什么位置，就是该位置的回文右边界】；

4、**C**：取得最大回文右边界时对应的中心位置。

*  ### 求 i 位置回文半径的步骤分析： ###

情况1：i 在 R 外(i >= R)：i 不在最大回文右边界里，那么无法利用之前的结论，i 位置的值只能通过往两边暴力扩得到。

情况2：i 在 R 内：【则可以利用之前已有的结果进行加速，i 位置的回文半径至少为 min(R - i, pArr\[i'\])】(i‘ 与 i 关于 C 对称，L 和 R 关于 C 对称)

2.1、（i’ -  pArr\[i'\]）>  L ：以 i' 为中心的回文字符串完全在 (L, R)范围内，则 i 位置的回文半径大小 = pArr\[i'\] 【其右边界小于 R 】；

2.2、（i’ - pArr\[i'\]）= L：以 i' 为中心的回文字符串左边界压线 L，则 i 位置的回文半径大小 >= pArr\[i'\]，即 >= R - i，至于是否能扩得更大，需要去暴力尝试【其回文右边界至少是 R，或许大于 R】；

2.3、（i’- pArr\[i'\]）< L ：以 i' 为中心的回文字符串左边界超出(L, R)范围，则 i 位置的回文半径大小 = R - i 【其右边界就是 R】。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

public class Manacher {
    
        public static int maxLcpsLength(String str){
            if(str == null || str.length() == 0){
                return 0;
            }
            // 把字符串处理为manachar类字符串，1221->#1#2#2#1#
            char[] chars = manacherString(str);
            int[] pArr = new int[chars.length];  // 回文半径数组
            int C = -1;  // 取得R时的回文中心
            int R = -1;  //  R-1为最大回文右边界，R是最大回文右边界的下一位
            int max = Integer.MIN_VALUE;
            //遍历每一个字符，计算以该字符为中心的回文字符串长度
            for(int i = 0; i < chars.length; i++){
                //况一： R <= i ,i 彻底在回文右边界的右侧，回文半径至少为 1 （它本身）
                //况二： R > i,
                //得到 i 位置回文半径至少的长度
                pArr[i] = R > i ? Math.min(R - i, pArr[C - (i - C)]) : 1;  // //C-(i-C)即 i'
                //从可能扩得更远的位置开始验证
                while(i + pArr[i] < chars.length && i - pArr[i] > -1){
                    if(chars[i + pArr[i]] == chars[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]);
            }
            // 返回最大回文字符串长度，因为我们的chars是改造过的，是原字符串的 2倍+1
            // 从中心开始，每个字符后面有一个#，即相当于*2，但中心字符只有一个，所以要-1
            return max - 1;
        }
    
        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 void main(String[] args) {
            String str1 = "abcdcba";
            System.out.println(maxLcpsLength(str1));
        }
    }

![20190706181936942.png][]

[20190706175325560.png]: /images/20211214/581b24ea7ad7462ca74e23a5e66bfc9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20211214/609516bbc13e4a4b83c7fcb73a848103.png
[20190706181936942.png]: /images/20211214/a29050022eec42a5b4190c1fad959ab4.png