問題：給定一個(gè)字符串咨油，求它的最長回文子串長度灵妨。
提示：如果一個(gè)字符串正著讀和反著讀是一樣的宿礁，那它就是回文串钉寝。下面是一些回文串的實(shí)例：ada,acca...
輸入：addaf
輸出：4

解題思路：

1.所有的回文串都是對稱的乍迄。長度為奇數(shù)回文串以最中間字符的位置為對稱軸左右對稱管引，而長度為偶數(shù)的回文串的對稱軸在中間兩個(gè)字符之間的空隙。所以我可以遍歷這個(gè)字符串的每個(gè)字符闯两，每次計(jì)算都假設(shè)每個(gè)字符是回文的中心（所以其實(shí)是在枚舉回文中心）然后將這個(gè)字符向左向右擴(kuò)展直至不重復(fù)為止褥伴，遍歷一次下來就能找到最大的回文子串。時(shí)間復(fù)雜度O(n^2)

代碼（C 環(huán)境：Xcode）

int func(char *s){
    int n,i,j,c,max;
    n = strlen(s);
    if(n < 1){
        return 0;
    }
    
    else{
        max = 0;
        for (i = 0; i < n; i++) { // i is the middle point of the palindrome

            for (j = 0; (i - j >= 0) && (i + j < n); j++){ // for the odd case
                if (s[i - j] != s[i + j]){
                    break;}
                c = j * 2 + 1;
            }
            if (c > max)
                max = c;

            for (j = 0; (i - j >= 0) && (i + j + 1 < n); j++){ // for the even case

                if (s[i - j] != s[i + j + 1]){
                    break;}
                c = j * 2 + 2;
            }
            if (c > max)
                max = c;
            
        }
    }
    return max;
}

存在的問題

1.代碼復(fù)雜
回文長度的奇偶性影響很大（回文中心是字符之間的空隙還是字符漾狼？）代碼是分開的重慢。
2.重復(fù)訪問
舉個(gè)例子

char: a b a b a
 i : 0 1 2 3 4

當(dāng)i==1，和i==2時(shí)逊躁，左邊的子串a(chǎn)ba分別被遍歷了一次似踱。

解決辦法：Manacher 算法

(1)Manacher算法首先對字符串做一個(gè)預(yù)處理，在所有的空隙位置(包括首尾)插入同樣的符號，要求這個(gè)符號是不會在原串中出現(xiàn)的核芽。這樣會使得所有的串都是奇數(shù)長度的囚戚。以插入*號為例：

aba:*a*b*a* //回文長度L=奇數(shù)
abba:*a*b*b*a*  //回文長度L=奇數(shù)

插入的是同樣的符號，且符號不存在于原串轧简，因此子串的回文性不受影響驰坊，原來是回文的串，插完之后還是回文的哮独，原來不是回文的拳芙，依然不會是回文。
(2)我們把一個(gè)回文串中最左或最右位置的字符與其對稱軸的距離稱為回文半徑皮璧。Manacher定義了一個(gè)回文半徑數(shù)組RL舟扎，用RL[i]表示以第i個(gè)字符為對稱軸的回文串的回文半徑。我們一般對字符串從左往右處理恶导，因此這里定義RL[i]為第i個(gè)字符為對稱軸的回文串的最右一個(gè)字符與字符i的距離浆竭。對于上面插入分隔符之后的兩個(gè)串，可以得到RL數(shù)組：

char: # a # b # a # 
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0 
i : 0 1 2 3 4 5 6
char: # a # b # b # a # 
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0 
i : 0 1 2 3 4 5 6 7 8

上面我們還求了一下RL[i]-1惨寿。通過觀察可以發(fā)現(xiàn)，RL[i]-1的值删窒，正是在原本那個(gè)沒有插入過分隔符的串中裂垦，以位置i為對稱軸的最長回文串的長度。那么只要我們求出了RL數(shù)組肌索，就能得到最長回文子串的長度蕉拢。
于是問題變成了，怎樣高效地求的RL數(shù)組诚亚。基本思路是利用回文串的對稱性晕换，擴(kuò)展回文串。
具體可以參考（關(guān)于Manacher我見過最詳細(xì)的帖）：
<a >Manacher傳送門</a>

代碼(C 環(huán)境：Xcode)

void make_odd(char *s){//pre-process the string, make  length be the odd
    int len_1,len_2,i;
    len_1 = strlen(s);
    len_2 = 2*len_1 + 1;
    for(i = len_1-1;i>=0;i--){
        
        s[2*i +1] = s[i];
        s[2*i]='*';
        
    }
    s[len_2-1]='*';//last_position
    s[len_2]='\0';
}
int func_2(char *s){
    int i,MaxRight,pos,MaxLen,RL[100];
    for(i=0;i<strlen(s);i++){
        RL[i] = 0;
    }//RL=[0]*len(s)
    MaxRight=0;
    pos=0;
    MaxLen=0;
    //for i in range(len(s)):
    for(i=0;i<strlen(s);i++){
        if(i<MaxRight){
               
               RL[i] = RL[2*pos-i]<MaxRight-i?RL[2*pos-i]:MaxRight-i;
               //RL[i]= min (RL[2*pos-i], MaxRight-i)
        }
        else{
                RL[i]=1;
        }
        while( i-RL[i]>=0 && i+RL[i]<strlen(s) && s[i-RL[i]]==s[i+RL[i]]){
                RL[i]+=1;
        }
        if(RL[i]+i-1>MaxRight){
                MaxRight=RL[i]+i-1;
                pos=i;
        }
        MaxLen=MaxLen>RL[i]?MaxLen:RL[i];//update MaxLen
}
    return MaxLen-1;
}

復(fù)雜度分析

空間復(fù)雜度：插入分隔符形成新串站宗，占用了線性的空間大姓⒆肌；RL數(shù)組也占用線性大小的空間梢灭，因此空間復(fù)雜度是線性的夷家。
時(shí)間復(fù)雜度：盡管代碼里面有兩層循環(huán)，但Manacher的時(shí)間復(fù)雜度是線性的敏释。由于內(nèi)層的循環(huán)只對尚未匹配的部分進(jìn)行库快，因此對于每一個(gè)字符而言，只會進(jìn)行一次钥顽，因此時(shí)間復(fù)雜度是O(n)义屏。

References

1.<a href =https://segmentfault.com/a/1190000003914228)>最長回文子串——Manacher 算法的python實(shí)現(xiàn) </a>
2.LeetCode:Longest Palindromic Substring 最長回文子串