[百度]2014百度校園招聘之最長回文串

給你一個字元串，找出該字元串中對稱的子字元串的最大長度。即求最大回文串。

即不使用技巧，窮舉所有可能。時間複雜度為o(n^3)（時間上最長，不推薦使用），空間複雜度為o(1)。

本思路是從最大長度的字串開始，而不是從最小開始。假如說給定的字元串為len，先周遊長度為len的字串是否為回文串，如果是停止，

如果不是周遊長度為len-1的字串是否是回文串，一次類推。

假設現在已經周遊到第 i 個字元，要找出以該字元為“中心”的最長對稱字元串，我們需要用另兩個指針分别向前和向後移動，直到指針到達字元串兩端或者兩個指針所指的字元不相等。因為對稱子字元串有兩種情況，是以需要寫出兩種情況下的代碼：

（1） 第 i 個字元是該對稱字元串的真正的中心，也就是說該對稱字元串以第 i 個字元對稱， 比如： “aba”

（2）第 i 個字元串是對稱字元串的其中一個中心。比如“abba”。

是以周遊到每個字元都要考慮兩種情況，它可能是在奇數個回文串中或者是在偶數個回文串中

算法的基本思路是這樣的：把原串每個字元中間用一個串中沒出現過的字元分隔#開來(統一奇偶)，同時為了防止越界，在字元串的首部也加入一個特殊符$，但是與分隔符不同。同時字元串的末尾也加入'\0'。算法的核心：用輔助數組p記錄以每個字元為核心的最長回文字元串半徑。也就是p[i]記錄了以str[i]為中心的最長回文字元串半徑。p[i]最小為1，此時回文字元串就是字元串本身。 

示例：原字元串 'abba’，處理後的新串 ' $#a#b#b#a#\0’，得到對應的輔助數組p=[0,1,1,2,1,2,5,2,2,1]。 

詳細請看：[算法]manacher算法之最大回文子串

相關連結：

[小米]2015小米校招之回文數判斷

[網易]字元串回文分割