最长回文子串

难度中等
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

众所周知，回文子串是以某一轴为中心，左右呈镜像对称，如何找到 s 中最长的回文子串呢？

1.暴力破解

暴力破解是最容易想到的一种解法，即以每个字符为中心，向左右两边扩，看扩出去的范围有多大，同时记录一个最大值。比如 s = "abhba"，最大回文子串即以 字符 h 为中心，左右扩到底。然而这种方法有个问题，无法应对偶回文，当 s ="abba"的时候，以每个字符为中心扩结果得到的最长回文子串长度为 1 ！明显是错误的！
所以为了解决上述无法应对偶回文的情况，需要引入特殊字符来解决，即在每一个字符左右添加上一个特殊字符进行占位，这样就可以解决这个问题
上述的 s ="abba" 就变成了 s ="#a#b#b#a#"，这样我们就可以通过暴力法解决！

以下为暴力法的代码

public char[] getSPString(String s){
        int len = s.length();
        char[] arr = new char[2 * len + 1];
        for(int i = 0 ;i < len;i++){
            arr[2 * i] = '#';
            arr[2 * i + 1] = s.charAt(i);
        }
        arr[2 * len] = '#';
        return  arr;
    }
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1){
            return s;
        }
        char[] res = getSPString(s);
        int len = res.length;
        int C = 0;   //最长回文串中心
        int max = 1;  //最长回文串长度

        for(int i = 0; i< len;i++){
            int j = 1;
            while(i - j >=0 && j + i < len){
                if(res[i - j] ==  res[i + j]){
                    j++;
                }else{
                    break;
                }
            }
            if(2 * j - 1 > max){
                C = i;
                max = 2 * j - 1;
            }   
        }
        return s.substring((C - max/2)/2 , (C+ max/2)/2);
    }

2.Manacher算法

暴力法的缺点在于，最坏情况下时间复杂度趋近于 O(n^2)!
而马拉车算法的关键在于通过定义一个最大右边界，不断地判断当前位置地情况，然后寻找当前位置地对称点，利用之前已经求出的信息，加速整个判断过程！注意：此过程也需要预先转换成特殊字符串进行处理！！！

首先我们定义几个概念：

1. 最大回文右边界 R ：即当前字符串中的回文子串达到的最右位置。例如 “#a#b#c#b#a#c#”，当到达第一个字符 ‘c’ 时，最大回文右边界为下标10！
2. 最大回文半径 max_Radius 和 存放对应位置的最大回文半径arr[ ] 数组： 回文半径就是当前回文中心到达右边界或者左边界的距离。如下图所示

3. 回文中心 C ：即当前最大右边界R的情况下，回文串的中心，与最大会问右边界互为对应关系。

接下来就是加速过程！

1. 当前位置 i 在最大回文右边界 R 的外边——以当前位置为中心往外扩，并更新 R 和 C
   当遍历到第一个字符’#’时，发现不能往外扩，即最大回文右边界就是下标 0 ，然后碰到 字符 ‘a’的时候，发现 i 大于 R ，故需要往外扩，然后发现能扩出去，即此时 R 到了下标 2！ C 也更新为了 i ！

2. 当前位置 i 在最大回文右边界 R 的里边——判断 i 的对称点 i’ 的情况！
   此时需要分三种情况：

   • 以 i’ 为中心的最大回文子串完全在最大左边界即将最大右边界R以C为中心对称过去）里边！如下图，此时 i 位置的最大回文半径 与 i’ 一样，都为 2！此时时间复杂度为O(1)
     

   • 以 i’ 为中心的最大回文子串超出最大左边界！如下图所示，此时 i’ 的回文串已经超出 L 到达了 左边的 K 字符，那么此时 i 的最大回文半径就是 R - i ，为什么此时不用扩呢？其实可以证明，如果此时可以扩，那么只有一种情况， 最右边的不是 E 而是 K ，但是如果是 K 的话，此时违反了 R 的最大回文右边界 的定义！即 R 一定至少大于等于最右边 E 的位置！所以此时 L 的左边一个字符和 R 右边的字符一定不等! 此时时间复杂度为O(1)
     

   • 以 i’ 为中心的最大回文子串正好在最大左边界上！即压线！如下图所示。此时以i位置为中心，以arr[i’]为半径，需要再往外扩！因为这时不确定 R 右边的字符是否满足条件！
     

综上，情况就是分为两大类，i 在回文右边界里边和外边！需要扩的两种情况，即 i 在 R 外边和压线，都是在不断地往右推动这个 R，所以整个过程总起来看就是在不断地往右推动着 R 前进，因为 R最多能到最右边，故整体的时间复杂度为 O(n)级别的！！！！！

下面直接上代码

public void manacher(String s) {
        if (s == null || s.length() <= 1) {
            return;
        }
        char[] sp = getSPString(s);
        int len = sp.length;
        int[] arr = new int[sp.length]; //最长回文半径数组
        int R = -1; //最大回文右边界
        int C = -1; //最大回文中心
        int max = -1; // 最长回文半径
        for (int i = 0; i < len; i++) {
            arr[i] = R > i ? Math.min(arr[2 * C - i] , R - i) : 1;
            while(i + arr[i] < len && i - arr[i] >= 0){
                if(sp[i + arr[i]] == sp[i - arr[i]]){
                    arr[i] ++;
                } else{
                    break;
                }
            }
            if(i + arr[i] > R){
                R = i +arr[i];
                C = i;
            }
            if(max < arr[i]){
                max  = arr[i];
                center = i;
            }
        }
    }

本作品采用《CC 协议》，转载必须注明作者和本文链接