马拉车算法（manacher）求最长回文子串

冷不防 2023-02-15 10:18 49阅读 0赞

关于回文字符串的概念大家可以大致去搜索一下，这里不赘述。

### 一、解题思路 ###

当前字符串

![20200605082139621.png][]

最长回文子串：

![20200605082216661.png][]

思路实际上很简单，就是遍历每一个元素，然后分别以这个元素为中心，向两边扩展，比如说现在i = 4，那么当前字符串是t，我们可以里面写一个循环，l = i - 1,r = i + 1，然后判断chars\[l\] == chars\[r\]看是否相等，如果相等继续i--，r++，再新型比较，记录一下最大值即可。下面这种情况需要注意：

![20200605082601401.png][]

当中心是连续的，那么最好的解决办法（不唯一）是如下：先将字符串变成这个鸟样子\#e\#a\#b\#c\#t\#t\#c\#b\#a\#b\#。中间插入一个特殊字符，就解决了这个问题，依然是遍历。暴力的解法，就是改成这个样子之后从前到后遍历，时间复杂度O(4n2 + 4n + 1)就等于O(n2)。

转换字符串：

public static char[] manacherString(String str){
            char[] chars = 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 ? '#':chars[index++];
            }
            return res;
        }

### 二、暴力解法 ###

public static int fuck(char[] chars){
            if(chars == null || chars.length == 0){
                return 0;
            }
            int max = Integer.MIN_VALUE;
            for(int i = 0;i < chars.length;i++){
                int l = i - 1;
                int r = i + 1;
                while(l >= 0 && r <= chars.length - 1 && chars[l] == chars[r]){
                    l--;
                    r++;
                }
                max = Math.max(max, r - l  - 1 );
            }
            return max / 2;
        }

### 三、manachere算法 ###

对于暴力的优化，依然是利用原来计算过的结果。时间复杂度O(n)

先看几个概念：

（1）回文半径数组arr：这个表示遍历字符串的每一个字符下标是i的时候，最长回文半径的值。例如ababac。转换成\#a\#b\#c\#b\#a\#c\#，那么数组arr = \[1,2,1,2,1,6,1,2,1,21,2,1\]。

（2）最右回文右边界r：省略了\#。当字符到了c时，那么r为

![202006050910142.png][]

r到了右边a的部分，当到了b的时候，回文就是他自己所以这个r也不变，r就相当于是以i为中心的最大半径，一直向右扩展。

（3）回文中心：也就是上面图c的位置就是回文中心。

**回文是以回文中心i和半径形成的对称字符串**

**先看这张图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

x表示进行到的当前位置，r表示最右回文右边界，中心表示回文中心，x1表示x的对称点r1表示对称半径。

**求arr的四种情况：**

（1）当前遍历的i位置不在r内，那么直接暴力扩展。

（2）遍历的位置在r内，且对称点的半径也在r内。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

回文中心范围，可以根据回文中心和r计算得出，找到x的对称点x1，去数组中找到对应的半径r1，发现半径在以回文中心范围内，那么直接x的数组值就是r1。

（3）遍历位置在r内，且对称点的半径超过了r。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2][]

r1超过了会问中心范围，这样我们也不用扩展，因为c和d必然不相同，即使对称点可以扩展出去，但是x是不能的因为回文中心范围整体是一个对称的，边界以外第一个元素不可能相同。所以x的半径直接等于边界和x位置的计算值。

（4）遍历位置在r内，如果压线了，刚好与边界相同。那么就可以先令数组的值等于边界与x的计算值或者等于半径值，在进行向外扩展。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3][]

以上几种情况分析，主要是根据回文的对称原理来做的！！！

综上所述，只有情况1和4需要暴力扩展，2和3都是直接可以拿到数值的时间复杂度O(1)。

public static int getManacherLen(String str){
            if(str == null || str.length() == 0){
                return 0;
            }
            char[] chars = manacherString(str);
            //回文半径数组
            int[] pArr = new int[chars.length];
            //回文中心
            int c = -1;
            //最右回文右边界
            int r = -1;
            int max =  Integer.MIN_VALUE;
            for(int i = 0;i < chars.length;i++){
                //情况2、3，选取最小的
                //情况4，如果刚好边界，那么两个值相等，取哪一个无所谓。
                //情况1，没在r内，设置为1代表自己
                // r - i边界值，2 * c - i 表示对称点的位置。
                pArr[i] = r > i ? Math.min(pArr[2 * c - i],r - i) : 1;
                while(i + pArr[i] < chars.length && i - pArr[i] > -1){
                    //如果是情况2、3，压根就不成立，只有情况4和情况1才有机会执行
                    if(chars[i + pArr[i]] == chars[i - pArr[i]]){
                        pArr[i]++;
                    }else{
                        break;
                    }
                }
                //更新r和回文中心
                if(i + pArr[i] > r){
                    r = i + pArr[i];
                    c = i;
                }
                max = Math.max(max,pArr[i]);
            }
            return max - 1;
        }

### 四、应用 ###

将一个字符串转换成一个回文字符串，所用长度最短。这个问题如果不会马拉车就很麻烦了，我们通过马拉车算法，我们改写马拉车算法，获取包含最后一个字符的最大半径然后将之前的逆序添加到末尾就可以了，abcd123321 => abcd123321dcba

import java.util.Stack;
    
    public class Main {
    
        public static String fuct(String str){
            if(str == null || str.length() == 0){
                return null;
            }
            char[] chars = manacherString(str);
            int[] arr = new int[chars.length];
            int index = -1;
            int r = -1;
            int max = Integer.MIN_VALUE;
            int maxContainsEnd = -1;
            for(int i = 0;i < chars.length;i++){
                arr[i] = r > i ? Math.min(arr[2 * index - i],r - i) : 1;
                while(i - arr[i] > -1 && i + arr[i] < chars.length){
                    if(chars[i - arr[i]] == chars[i + arr[i]]){
                        arr[i]++;
                    }else{
                        break;
                    }
                }
                if(i + arr[i] > r){
                    r = i + arr[i];
                    index = i;
                }
                if(r == chars.length){
                    maxContainsEnd = arr[i];
                    break;
                }
            }
            char[] res = new char[str.length() - maxContainsEnd + 1];
            for(int i = 0;i < res.length;i++){
                res[res.length - 1 - i] = chars[i * 2 + 1];
            }
            return String.valueOf(res);
        }
    
        public static char[] manacherString(String str){
            char[] chars = 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 ? '#':chars[index++];
            }
            return res;
        }
    
        public static String getStr(String string){
            return string + fuct(string);
        }
    
    
        public static void main(String[] args) {
    
            System.out.println(getStr("abcd123321"));
        }
    
    
    }

[20200605082139621.png]: https://img-blog.csdnimg.cn/20200605082139621.png
[20200605082216661.png]: https://img-blog.csdnimg.cn/20200605082216661.png
[20200605082601401.png]: https://img-blog.csdnimg.cn/20200605082601401.png
[202006050910142.png]: https://img-blog.csdnimg.cn/202006050910142.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200605094420481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200605094635810.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200605094834664.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200605095011664.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70