LeetCode 5.Longest Palindromic S

Leetcode : LongestPalindromicSubString
Diffculty：Medium

求最长回文子串。
这是一个在面试中比较常出现的算法题。最优解法是Manacher算法，实际上用的是动态规划的思路，首先通过增加间隔符，将结果变为找aba类型的回文串，然后利用已经找到的回文串结果，逐个向后查找更长的回文串。只需遍历一遍字符串即可。

题目

给一个字符串，找出其中最长的回文子串。
注意 aba 和 abba 都属于回文字符串。

目前有两种解法：
1）Manacher算法：时间复杂度O(N)
2）中心点扩散法：时间复杂度O(N^2)

Manacher算法参考思路：https://segmentfault.com/a/1190000003914228

解法

Manacher算法：

   /**
     * Manacher 算法
     * 充分利用回文特性，将字符中间插入 # 将单双回文统一转化为单回文问题
     * 然后维护一个数组p，该数组保存以 i 点为中心，最长的回文半径。
     * 那么p[i]-1 就是原字符中，以i为中心的回文长度
     * 那么问题的结果就是 max(p[i]) - 1
     *
     * 重点在于计算数组p
     *
     * 时间复杂度：O(N)
     */
    public static String manacher(String str){
        char[] t = preprocess(str);
        int[] p = new int[t.length];    // p[i] 表示以p为中心的最长的回文半径


        int mid = 0;        // 已触及的最右边的回文串 在p数组中的 索引 即 p[i] 的 i
        int maxRight = 0;   // 已触及的最右边的回文串，即 p[i]的值


        int length = 0; // 存储p数组中最大的值
        int center = 0; // 该最大值的中心index

        for(int i=1; i<t.length-1; i++){
            int mirror = 2*mid -i;  // i相对于mid的对称镜像位置
            if(i < maxRight){
                // i 在maxRight的左边
                // 则p[i] 可以暂时赋值为 镜像位置和maxRight-1 之间的最小值
                // 如果p[mirror] 小于maxRight-i 那么 p[i] 肯定是等于 p[mirror]
                // 如果p[mirror] 大于maxRight-i 那么 p[i] 至少等于 maxRight-i 由于 maxRight之后还没有比较过，需要从maxRight+1开始关于i对称进行比较。

                if(p[mirror] < maxRight-i){ // 注意 这里必须是小于。只有小于边界才能确定 p[i]=p[mirror] 等于只能确定至少是这样
                    p[i] = p[mirror];
                    // 已得到p[i] 结果，与length比较
                    if(p[i] > length){
                        length = p[i];
                        center = i;
                    }
                    continue;
                }else{
                    p[i] = maxRight-i;
                }
            }

            // p[i] 向两边扩散，相等则值+1。直到找到不等的为止
            while(t[i+(1+p[i])] == t[i-(1+p[i])]){
                p[i]++;
            }

            // d得到最终p[i]的值以后
            // 如果 maxRight 在 i+p[i] 左边
            // 则maxRight=i+p[i] 顺便将回文中点置为i 即 mid=i;
            if(i+p[i] > maxRight){
                mid = i;
                maxRight = i + p[i];
            }

            // 把当次p[i] 计算结果与 最长结果比较并替换
            if(p[i] > length){
                length = p[i];
                center = i;
            }
        }
        return str.substring((center-1-length)/2, (center-1+length)/2);
    }


    // 预处理 处理成 $#a#b#c#d#e#@ 的形式
    // 头部$ 尾部@ 然后用# 隔开每一个元素
    // 由于回文字串会有奇数串和偶数串
    // 转为为 #a#b#a# 或者 #a#b#b#a# 以后，长度统一为了奇数个
    private static char[] preprocess(String str){
        char[] t = new char[str.length()*2 + 3];
        t[0] = '$';                 //起始边界
        t[str.length()*2 + 2] = '@';  //结束边界
        for(int i=0; i<str.length(); i++){
            t[2*i +1] = '#';
            t[2*i +2] = str.charAt(i);
        }
        t[str.length()*2 + 1] = '#';    //补上最后一个#

        return t;
    }

中心点扩散法

//回文子串结果
    static int lIndex = 0;
    static int rIndex = 0;
    static int maxLength = 0;


    /**
     * 中心点扩散法, 通过了leetcode
     * @param str
     * @return
     */
    public static String longestPalindrome(String str){
        if(str == null || str.length() <=2){
            return str;
        }

        for(int i=0; i<str.length(); i++){
            searchPalind(str, i, i);
            searchPalind(str, i, i+1);
        }
        // 最后仅执行一次substring
        return str.substring(lIndex, rIndex);
    }

    /**
     * 从中间向两边找回文字串在 str 中的最大索引范围。
     * @param str
     * @param low
     * @param high
     */
    private static void searchPalind(String str, int low, int high){
        while(low>=0 && high<str.length()){
            if(str.charAt(low) == str.charAt(high)){
                if(high-low+1 > maxLength){
                    lIndex = low;
                    rIndex = high+1;
                    maxLength = high - low + 1;
                }
            }else{
                // 如果不等于就退出
                return;
            }
            low--;high++;
        }
        return;
    }