Leetcode : LongestPalindromicSubString
Diffculty：Medium

求最長回文子串。
這是一個(gè)在面試中比較常出現(xiàn)的算法題。最優(yōu)解法是Manacher算法，實(shí)際上用的是動態(tài)規(guī)劃的思路，首先通過增加間隔符，將結(jié)果變?yōu)檎襛ba類型的回文串，然后利用已經(jīng)找到的回文串結(jié)果，逐個(gè)向后查找更長的回文串。只需遍歷一遍字符串即可。

題目

給一個(gè)字符串，找出其中最長的回文子串。
注意 aba 和 abba 都屬于回文字符串。

目前有兩種解法：
1）Manacher算法：時(shí)間復(fù)雜度O(N)
2）中心點(diǎn)擴(kuò)散法：時(shí)間復(fù)雜度O(N^2)

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

解法

Manacher算法：

   /**
     * Manacher 算法
     * 充分利用回文特性，將字符中間插入 # 將單雙回文統(tǒng)一轉(zhuǎn)化為單回文問題
     * 然后維護(hù)一個(gè)數(shù)組p，該數(shù)組保存以 i 點(diǎn)為中心，最長的回文半徑。
     * 那么p[i]-1 就是原字符中，以i為中心的回文長度
     * 那么問題的結(jié)果就是 max(p[i]) - 1
     *
     * 重點(diǎn)在于計(jì)算數(shù)組p
     *
     * 時(shí)間復(fù)雜度：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數(shù)組中的 索引 即 p[i] 的 i
        int maxRight = 0;   // 已觸及的最右邊的回文串，即 p[i]的值


        int length = 0; // 存儲p數(shù)組中最大的值
        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] 可以暫時(shí)賦值為 鏡像位置和maxRight-1 之間的最小值
                // 如果p[mirror] 小于maxRight-i 那么 p[i] 肯定是等于 p[mirror]
                // 如果p[mirror] 大于maxRight-i 那么 p[i] 至少等于 maxRight-i 由于 maxRight之后還沒有比較過，需要從maxRight+1開始關(guān)于i對稱進(jìn)行比較。

                if(p[mirror] < maxRight-i){ // 注意 這里必須是小于。只有小于邊界才能確定 p[i]=p[mirror] 等于只能確定至少是這樣
                    p[i] = p[mirror];
                    // 已得到p[i] 結(jié)果，與length比較
                    if(p[i] > length){
                        length = p[i];
                        center = i;
                    }
                    continue;
                }else{
                    p[i] = maxRight-i;
                }
            }

            // p[i] 向兩邊擴(kuò)散，相等則值+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] 順便將回文中點(diǎn)置為i 即 mid=i;
            if(i+p[i] > maxRight){
                mid = i;
                maxRight = i + p[i];
            }

            // 把當(dāng)次p[i] 計(jì)算結(jié)果與 最長結(jié)果比較并替換
            if(p[i] > length){
                length = p[i];
                center = i;
            }
        }
        return str.substring((center-1-length)/2, (center-1+length)/2);
    }


    // 預(yù)處理 處理成 $#a#b#c#d#e#@ 的形式
    // 頭部$ 尾部@ 然后用# 隔開每一個(gè)元素
    // 由于回文字串會有奇數(shù)串和偶數(shù)串
    // 轉(zhuǎn)為為 #a#b#a# 或者 #a#b#b#a# 以后，長度統(tǒng)一為了奇數(shù)個(gè)
    private static char[] preprocess(String str){
        char[] t = new char[str.length()*2 + 3];
        t[0] = '$';                 //起始邊界
        t[str.length()*2 + 2] = '@';  //結(jié)束邊界
        for(int i=0; i<str.length(); i++){
            t[2*i +1] = '#';
            t[2*i +2] = str.charAt(i);
        }
        t[str.length()*2 + 1] = '#';    //補(bǔ)上最后一個(gè)#

        return t;
    }

中心點(diǎn)擴(kuò)散法

//回文子串結(jié)果
    static int lIndex = 0;
    static int rIndex = 0;
    static int maxLength = 0;


    /**
     * 中心點(diǎn)擴(kuò)散法, 通過了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);
        }
        // 最后僅執(zhí)行一次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;
    }