首先，得先了解什麼是回文串。回文串就是正反讀起來就是一樣的，如“abcdcba”。我們要是直接采用暴力方法來查找最長回文子串，時間複雜度為O（n^3）,好一點的方法是枚舉每一個字元，比較較它左右距離相鄰的點是否相等，我們姑且稱之為中心檢測法，時間複雜度為O（n^2）。
當我們遇到字元串為“aaaaaaaaa”，之前的算法就會發生各個回文互相重疊的情況，會産生重複計算，然後就産生了一個問題，能否改進？答案是能，1975年，一個叫Manacher發明了Manacher Algorithm算法，俗稱馬拉車算法，其時間複雜為O(n)。該算法是利用回文串的特性來避免重複計算的。
在中心檢測法中，我們在周遊的過程要考慮到回文串長度的奇偶性，比如說“abba”的長度為偶數，“abcba”的長度為奇數，這樣在尋找最長回文子串的過程要分别考奇偶的情況，是否可以統一處理了？
Manacher算法：
一）第一步是改造字元串S，變為T，其改造的方法如下：
在字元串S的字元之間和S的首尾都插入一個“#”，如：S=“abba”變為T="#a#b#b#a#" 。我們會發現S的長度是4，而T的長度為9，長度變為奇數了！！那S的長度為奇數的情況時，變化後的長度還是奇數嗎？我們舉個例子，S=“abcba”，變化為T=“#a#b#c#b#a#”，T的長度為11，是以我們發現其改造的目的是将字元串的長度變為奇數，這樣就可以統一的處理奇偶的情況了。
二）第二步，為了改進回文互相重疊的情況，我們将改造完後的T[ i ] 處的回文半徑存儲到數組P[ ]中，P[ i ]為新字元串T的T[ i ]處的回文半徑，表示以字元T[i]為中心的最長回文字串的最端右字元到T[i]的長度，如以T[ i ]為中心的最長回文子串的為T[ l, r ]，那麼P[ i ]=r-i+1。這樣最後周遊數組P[ ]，取其中最大值即可。若P[ i ]=1表示該回文串就是T[ i ]本身。舉一個簡單的例子感受一下：
數組P有一性質，P[ i ]-1就是該回文子串在原字元串S中的長度 ，那就是P[i]-1就是該回文子串在原字元串S中的長度，至于證明，首先在轉換得到的字元串T中，所有的回文字串的長度都為奇數，那麼對于以T[i]為中心的最長回文字串，其長度就為2*P[i]-1,經過觀察可知，T中所有的回文子串，其中分隔符的數量一定比其他字元的數量多1，也就是有P[i]個分隔符，剩下P[i]-1個字元來自原字元串，是以該回文串在原字元串中的長度就為P[i]-1。
另外，由于第一個和最後一個字元都是#号，且也需要搜尋回文，為了防止越界，我們還需要在首尾再加上非#号字元，實際操作時我們隻需給開頭加上個非#号字元，我就直接使用美元吧$,結尾不用加的原因是字元串的結尾辨別為'\0'，等于預設加過了。這樣原問題就轉化成如何求數組P[ ]的問題了。
三）如何求數組P [ ]
從左往右計算數組P[ ]， Mi為之前取得最大回文串的中心位置，而R是最大回文串能到達的最右端的值。
1）當 i <=R時，如何計算 P[ i ]的值了？毫無疑問的是數組P中點 i 之前點對應的值都已經計算出來了。利用回文串的特性，我們找到點 i 關于 Mi 的對稱點 j ，其值為 j= 2*Mi-i 。因，點 j 、i 在以Mi 為中心的最大回文串的範圍内（[L ,R]），
a）那麼如果P[j] <R-i （同樣是L和j 之間的距離），說明，以點 j 為中心的回文串沒有超出範圍[L ,R]，由回文串的特性可知，從左右兩端向Mi周遊，兩端對應的字元都是相等的。是以P[ j ]=P[ i ]（這裡得先從點j轉到點i 的情況），如下圖：
if(i<mx)
{
p[i]=min(p[2*id-i],mx-i);
}
else
{
p[i]=1;
} 程式也是可以運作的，但這樣是不是又變成了中心檢測法了？我認為Manacher算法的最大優點在于利用回文串對稱的性質，在處理p數組的時候，利用指針i,j的同步性，避免了比對失敗後的下标回退，因而将時間複雜度優化為了O(n)。
相應的代碼如下：
1 char x[MAX];
2 char s_new[MAX*2];
3 int p[MAX*2];
4 int Init()
5 {
6 int i,j,len;
7 len=strlen(x);
8 s_new[0]='$';
9 s_new[1]='#';
10 j=2;
11 for(i=0; i<len; i++)
12 {
13 s_new[j++]=x[i];
14 s_new[j++]='#';
15 }
16 s_new[j]='\0';
17 return j;
18 }
19 int Manacher()
20 {
21 int i;
22 int len=Init();
23 int max_len=-1;
24 int id;
25 int mx=0;
26 for (i=1; i<len; i++)
27 {
28 if(i<mx)
29 {
30 p[i]=min(p[2*id-i],mx-i);
31 }
32 else
33 {
34 p[i]=1;
35 }
36 while (s_new[i-p[i]]==s_new[i+p[i]])
37 {
38 p[i]++;
39 }
40 if(mx<i+p[i])
41 {
42 id=i;
43 mx=i+p[i];
44 }
45 }
46 for(i=1; i<len; i++)
47 {
48 if(max_len<p[i]-1)
49 {
50 max_len=p[i]-1;
51 }
52 }
53 return max_len;
54 } 作者：王陸