一钧大、背景

最近在LintCode上面刷題時(shí)遇到了一個(gè)求解最長(zhǎng)回文子串的問(wèn)題，這個(gè)題目可以使用暴力的方式去進(jìn)行求解罩旋，但算法的時(shí)間復(fù)雜度至少就是O(n^2)級(jí)別了啊央，后面看討論區(qū)時(shí)發(fā)現(xiàn)了一個(gè)比較有意思的算法，也就是今天的主題－－Manacher算法涨醋，用這個(gè)算法可以只需要O(n)級(jí)別的時(shí)間復(fù)雜度瓜饥，花時(shí)間去學(xué)習(xí)了一下，感覺(jué)確實(shí)是挺好的一種思路浴骂，這里就來(lái)記錄一下乓土。

二、算法過(guò)程

1.簡(jiǎn)介

Manacher算法是通過(guò)求解一個(gè)中心點(diǎn)溯警，在距離這個(gè)點(diǎn)R長(zhǎng)度以內(nèi)都是關(guān)于這個(gè)點(diǎn)左右對(duì)稱的趣苏，也就是說(shuō)這個(gè)長(zhǎng)度為2R的字符串是一個(gè)回文串，最后再比較大小梯轻，求出最大的長(zhǎng)度2R及其中心點(diǎn)食磕，最后就得出了題解，并且整個(gè)過(guò)程就掃描整個(gè)字符串一遍喳挑。這里也可以看出彬伦，因?yàn)橐蠡匚淖哟闹行狞c(diǎn)，這個(gè)中心點(diǎn)也是唯一的伊诵，所以它只能處理字符串是奇數(shù)位的情況单绑。因此我們第一步就是把字符串長(zhǎng)度變?yōu)槠鏀?shù)，這里就要使用一個(gè)非常巧妙的方式曹宴，把字符串中每個(gè)字符使用一個(gè)其它字符號(hào)包圍起來(lái)搂橙，，這里以“５烟梗”號(hào)為例份氧，可以想象一下唯袄，要把每個(gè)字符都使用''#''號(hào)包裹，那么需要的#號(hào)總是要比原來(lái)的字符串長(zhǎng)度多一位蜗帜，才能保證每個(gè)字符都能被插入到#與#中間恋拷，簡(jiǎn)單舉個(gè)例子

aa -> #a#a# 
aaa -> #a#a#a#

可以看到不管原來(lái)的字符串長(zhǎng)度是什么，奇數(shù)加偶數(shù)結(jié)果肯定是奇數(shù)的厅缺，進(jìn)行這一步處理后蔬顾，就可以開(kāi)始求最長(zhǎng)回文子串的半徑R了。

2.求解最長(zhǎng)回文子串半徑

這里可以先借助兩個(gè)變量center湘捎、right分別記錄回文子串對(duì)應(yīng)的中心點(diǎn)和右端點(diǎn)诀豁，看看下圖，

r[i]=right>i?(Math.min(r[2*center-i], right-i)):1;

這里借助一個(gè)輔助的數(shù)組r[]來(lái)記錄回文子串的半徑R旦事，r[i]表示的是以i為中心點(diǎn)的回文字符串的半徑長(zhǎng)度(初始情況下為1)魁巩，知道r[i]后，就可以繼續(xù)把索引向左右兩邊擴(kuò)充姐浮，也就是看i+r[i]與i-r[i]左右端點(diǎn)的位置所對(duì)應(yīng)的字符是否相等谷遂，相等的話就把回文半徑r[i]繼續(xù)擴(kuò)充，直到不相等為止单料。進(jìn)行這一輪擴(kuò)充后，就去看看之前的右端點(diǎn)right是否小于回文子串?dāng)U充后的右端點(diǎn)i+r[i],小于就直接更新右端點(diǎn)和中心點(diǎn)点楼，不小于就說(shuō)明當(dāng)前回文子串還是在當(dāng)前right端點(diǎn)的內(nèi)部扫尖。

3.全部代碼

public class Test200 {

    public String longestPalindrome(String s) {
        // write your code here
        StringBuilder builder = new StringBuilder();
       // 防止左端點(diǎn)越界
        builder.append("&#");
        char[] c = s.toCharArray();
        for (int i=0;i < c.length;i++) {
            builder.append(c[i]+"#");
        }
        String newStr = builder.toString();
        c = newStr.toCharArray();
        // 回文半徑
        int[] r = new int[newStr.length()];
        // 回文子串最大右端點(diǎn)、中心點(diǎn)
        int right=0, center=0;
        // 最大回文半徑掠廓、最大中心點(diǎn)
        int maxR=0, maxC=0;

        for (int i=1;i < c.length;i++) {
　　　// 以i為中心點(diǎn)的回文半徑换怖，可以重復(fù)利用以及匹配過(guò)對(duì)稱點(diǎn)的半徑
            r[i]=right>i?(Math.min(r[2*center-i], right-i)):1;
            while (i+r[i]<c.length && c[i+r[i]]==c[i-r[i]]) {
                ++r[i];
            }
            // 更新右端點(diǎn)和中心點(diǎn)
            if (right < i+r[i]) {
                right = i+r[i];
                center = i;
            }
            // 更新最大半徑和最大中心點(diǎn)
            if (maxR < r[i]) {
                maxR = r[i];
                maxC = i;
            }
        }
        // 計(jì)算在原字符串中的起始點(diǎn)
        int start = (maxC-maxR)/2;
        return s.substring(start, start+maxR-1);
    }

    public static void main(String[] args) {
        String s = "aa";
        Test200 test = new Test200();
        System.out.println(test.longestPalindrome(s));
    }
}

三、總結(jié)

整體來(lái)說(shuō)蟀瞧，理解清楚了沉颂，這個(gè)算法確實(shí)是挺巧妙的条摸，就暫時(shí)到這里了。
參考：https://www.felix021.com/blog/read.php?2040