Manacher算法昭娩，又叫“馬拉車”算法，可以在時間復(fù)雜度為O(n)的情況下求解一個字符串的最長回文子串長度的問題。

一浦楣、回文子串的一般解法

比較簡單的思路是將字符串的每一個字符作為回文子串的中心對稱點踱蠢，每次保存前面求得的回文子串的最大值火欧，最后得到的就是最長的回文子串的長度棋电，這種方式的時間復(fù)雜度是O(n^2)。在求解過程中苇侵，基數(shù)的回文子串與偶數(shù)的回文子串是不一樣的赶盔。比如最長回文子串為aba，對稱中心就是b榆浓，如果最長回文子串為abba于未，則對稱中心應(yīng)該為兩個b之間，為了解決這個問題陡鹃，可以在每個字符兩邊加上一個符號烘浦，具體什么符號（是字符串里面的符號也行）對結(jié)果沒有影響，比如加上“#”萍鲸，則上述的兩個序列變成了#a#b#a#和#a#b#b#a#闷叉，求出的長度分別為6和9，再除以2就可以得到最后的結(jié)果3和4脊阴。這種方式的時間復(fù)雜度太高握侧，下面介紹時間復(fù)雜度為O(n)的Manacher算法。

二嘿期、Manacher算法中的基礎(chǔ)概念

在進行Manacher算法時藕咏，字符串都會進行上面的進入一個字符處理，比如輸入的字符為acbbcbds秽五，用“#”字符處理之后的新字符串就是#a#c#b#b#c#b#d#s#孽查。

1、回文半徑數(shù)組radius

回文半徑數(shù)組radius是用來記錄以每個位置的字符為回文中心求出的回文半徑長度坦喘，如下圖所示盲再，對于p1所指的位置radius[6]的回文半徑是5，每個位置的回文半徑組成的數(shù)組就是回文數(shù)組瓣铣，所以#a#c#b#b#c#b#d#s#的回文半徑數(shù)組為[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]答朋。

要處理的字符串

2秽梅、最右回文右邊界R

一個位置最右回文右邊界指的是這個位置及之前的位置的回文子串卿樱，所到達的最右邊的地方。比如對于字符串#a#c#b#b#c#b#d#s#医瘫，求它的每個位置的過程如下：

最右回文右邊界R過程

最開始的時候R=-1蓖救，到p=0的位置洪规，回文就是其本身，最右回文右邊界R=0;p=1時循捺，有回文串#a#斩例，R=2；p=2時从橘，R=2;P=3時念赶，R=6;p=4時础钠，最右回文右邊界還是p=3時的右邊界，R=6,依次類推叉谜。

3旗吁、最右回文右邊界的對稱中心C

就是上面提到的最右回文右邊界的中心點C，如下圖停局，p=4時阵漏，R=6，C=3

最右回文右邊界的對稱中心C

三翻具、Manacher算法的流程

首先大的方面分為兩種情況：

第一種情況：下一個要移動的位置在最右回文右邊界R的右邊履怯。

比如在最開始時，R=-1,p的下一個移動的位置為p=0裆泳，p=0在R=-1的右邊叹洲；p=0時，此時的R=0工禾，p的下一個移動位置為p=1运提，也在R=0的右邊。

在這種情況下闻葵，采用普遍的解法民泵，將移動的位置為對稱中心，向兩邊擴槽畔，同時更新回文半徑數(shù)組栈妆，最右回文右邊界R和最右回文右邊界的對稱中心C。

第二種情況：下一個要移動的位置就是最右回文右邊界R或是在R的左邊

在這種情況下又分為三種：

1厢钧、下一個要移動的位置p1不在最右回文右邊界R右邊鳞尔，且cL<pL。

p2是p1以C為對稱中心的對稱點早直；

pL是以p2為對稱中心的回文子串的左邊界;

cL是以C為對稱中心的回文子串的左邊界寥假。

這種情況下p1的回文半徑就是p2的回文半徑radius[p2]。

p1<=R且cL<pL

2霞扬、下一個要移動的位置票p1不在最右回文右邊界R的右邊糕韧，且cL>pL。

p2是p1以C為對稱中心的對稱點喻圃；

pL是以p2為對稱中心的回文子串的左邊界萤彩；

cL是以C為對稱中心的回文子串的左邊界。

這種情況下p1的回文半徑就是p1到R的距離R-p1+1级及。

p1<=R且cL>pL

3乒疏、下一個要移動的位置票p1不在最右回文右邊界R的右邊额衙，且cL=pL饮焦；

p2是p1以C為對稱中心的對稱點怕吴；

pL是以p2為對稱中心的回文子串的左邊界；

cL是以C為對稱中心的回文子串的左邊界县踢。

這種情況下p1的回文半徑就還要繼續(xù)往外擴转绷，但是只需要從R之后往外擴就可以了，擴了之后更新R和C硼啤。

p1<=R且cL==pL

四议经、Manacher時間復(fù)雜度分析

從上面的分析中，可以看出谴返，第二種情況的1煞肾，2的求某個位置的回文半徑的時間復(fù)雜度是O(1)，對于第一種情況和第二種情況的3嗓袱，R是不斷的向外擴的籍救，不會往回退，而且尋找回文半徑時渠抹，R之內(nèi)的位置是不是進行判斷的蝙昙，所以對整個字符串而且，R的移動是從字符串的起點移動到終點梧却，時間復(fù)雜度是O(n),所以整個manacher的時間復(fù)雜度是O(n)奇颠。

五、Manacher的代碼實現(xiàn)

public static void main(String[] args) {
        String str = "abcdcbafabcdck";
        //String str = "acbbcbds";
        System.out.println(manacher(str));
    }

    public static char[] manacherString(String str){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            sb.append("#");
            sb.append(str.charAt(i));
        }
        sb.append("#");
        return sb.toString().toCharArray();
    }

    public static int manacher(String str){
        if(str == null || str.length() < 1){
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] radius = new int[charArr.length];
        int R = -1;
        int c = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < radius.length; i++) {
            radius[i] = R > i ? Math.min(radius[2*c-i],R-i+1):1;
            while(i+radius[i] < charArr.length && i - radius[i] > -1){
                if(charArr[i-radius[i]] == charArr[i+radius[i]]){
                    radius[i]++;
                }else{
                    break;
                }
            }
            if(i + radius[i] > R){
                R = i + radius[i]-1;
                c = i;
            }
            max = Math.max(max,radius[i]);
        } 
        return max-1;
    }