曼切斯特算法-最长回文子串

参考：https://mp.weixin.qq.com/s/t7Q0slX3q8Qlhg8F8pXrZQ

基本概念

什么是最长回文子串？
从左往右和从右往左遍历字符串得到的字符串相等
或者说：以中间某个字符向两边扩展得到的字符串相等，也可能是以中间两个相等字符向外扩展得到的字符串相等

曼切斯特算法的核心

• 暴力破解的方法
  以一个字符或者两个相等的字符向外扩展得到的字符串相等的思路：O（n^2）
• 曼切斯特算法
  基本思想：善用之前已经计算过的回文字符串长度，利用对称性来减少计算的步骤，达到O（n）的是时间复杂度
  解题关键点：
  1. 奇数偶数个字符串能否统一，可以通过插入特殊字符串解决
  2. 每次要记录以当前字符串为中心的回文字符串长度，并记录目前为止向右延伸最长的回文字符串中心，这个信息在后续需要使用：主要是以它为中心，利用对称性来节省时间
  3. 如何利用2中的思路求解后面的回文字符串长度，分析如下，：
     假设目前以下标index为中心的回文字符串向右延伸最大，主要有以下几种情况：

  1). j、k1关于index对称且k1在在index的最右延伸范围之内
  - 如果j的最长回文字符串等于或超过了i的左边，则以k1为中心的回文字符串需要继续以index的最右边界往两边扩展找如图（2）（3）所示
  - 如果j的最长回文字符串未到达index的左边，则以k1为中心的回文字符串等于以j为中心的回文字符串,如图中（1）所示。你可以假设k1的回文字符串还能往外延伸，则根据对称性，以j为中心的回文字符串也能往外延伸，矛盾。
  2) k2在index的最右延伸范围之外，前面没有可用的信息了，只能往两边找了

曼切斯特算法-最长回文子串示意图.jpg

4. 基于1、2、3就可以开始写代码了

代码实现

class Solution {
    
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        /**
         * 第一步：特殊处理下字符串,处理成奇数个字符串
         */
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            sb.append("#");
        }
        String calS = sb.toString();

        int maxLen = 0;
        int maxIndex = 0;

        /**
         * 第二步：一个新数组记录以i为中心的最大字符字串的长度--dp[i]
         * 一个变量记录当前最右延伸的下标i--index
         * dp[i]向右延伸到i+dp[i]
         */
        int[] dp = new int[calS.length()];
        int index = 0;
        for (int i = 1; i < calS.length() - 1; i++) {
            //先看i是否在dp[index]+index范围内
            if(dp[index] + index > i){
                //则可以利用关于index对称的左侧，j=2*index-i,dp[j],看j-dp[j]与index-dp[index]的大小关系
                int j = 2*index - i;
                if(j- dp[j] > index -dp[index]){
                    //未超过index延伸的最左边
                    dp[i] = dp[j];
                } else{
                    //dp[i] = dp[j]; //【bug1】：dp[i]初始值不是dp[j],dp[j]也是可能超越index左边界往外延伸的
                    dp[i] = dp[index]+index-i; //i到index最右边的距离
                    //dp[i]需要从index延伸的最右边开始（不用包括最右边界）匹配
                    int rightStart = dp[index] + index + 1;
                    int leftStart = 2*i - rightStart;
                    while(rightStart < calS.length() && leftStart >= 0 && calS.charAt(leftStart) == calS.charAt(rightStart)){
                        dp[i]++;
                        rightStart++;
                        leftStart--;
                    }
                    //更新index
                    index = i;
                }
            } else{
                //暴力往两边扩展
                int rightStart = i+1;
                int leftStart = i-1;
                while(rightStart < calS.length() && leftStart >= 0 && calS.charAt(leftStart) == calS.charAt(rightStart)){
                    dp[i]++;
                    rightStart++;
                    leftStart--;
                }
                //更新index
                index = i;
            }
            //更新最大长度
            if(dp[i] > maxLen){
                maxIndex = i;
                maxLen = dp[i];
            }
        }
        /**
         * 因为做了特殊处理，所以需要特殊处理回到原字符串,假设起点为下标为x,则x=maxIndex-maxLen/2, 
         *举例子maxLen等于奇数或者偶数分别验证下
         */
        int startIndex = (maxIndex - maxLen)/2;

        return s.substring(startIndex, startIndex + maxLen);
    }
}

自己编码的过程中遇到的问题：对于图中的（2）、（3）情况，我直接初始化dp[i]=dp[j], 这样是不对的，因为dp[j]也是很有可能超过index覆盖的范围往两边延伸的，正确的应该是dp[i]=dp[index]+index-i.(自己好好体会下，就是i离index最右侧的距离)

5. 对于manchester算法求最长回文字符串的一些思考
   manchester相对于暴力破解法的优势体现在什么情况下？
   这个跟字符串的规律有关：
   • 如果字符串的大部分回文字符串都不长，则manchester和暴力破解法时间复杂度相差不大
   • 如果字符串的大部分回文字符串较长，则manchester算法相对于暴力破解有很大的优势。因为后面回文字符串的求解可以很好的利用前面的回文字符串结果，节约时间。