字符串

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

2018-11-05  本文已影响0人  活出野性的自己

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

基本概念

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

曼切斯特算法的核心
曼切斯特算法-最长回文子串示意图.jpg
  1. 基于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最右侧的距离)

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

猜你喜欢

热点阅读