在中心擴充套件法中我們考慮了奇數和偶數兩種情況，而馬拉車演算法對它進行統一的思想是：在原字串的字元之間和首尾都插入一個字母

char* Init_manacher(char* s){    char* s_new = (char*)malloc(sizeof(char)*(2 * strlen(s) + 1));    int i = 0, j = 1;    s_new[0] = '#';    for (; i < strlen(s); i++, j++)    {        s_new[j++] = s[i];        s_new[j] = '#';    }    s_new[j] = '\0';    return s_new;}

s_new的長度變為了奇數，不管原來的字串是否奇數，這樣就可以統一處理奇數偶數長度了。

演算法的關鍵是：定義並計算陣列P[i]，（P[i]表示以字元s_new[i]為中心的最長迴文子串的最右端字元到s_new[i]的距離，俗稱迴文半徑），算出P[i]的每一個值，求出最大的迴文半徑，就得出最長迴文子串。

所以問題就轉化為求陣列P[i]

馬拉車演算法

圖中，

id ：為當前已經計算過的字串中，觸及右邊最遠的子串的中心點

mx ：觸及右邊最遠子串所觸及的最遠的點

j是i的對稱點，根據對稱性可以得出，i + j = 2 * id，從而得出：

i的對稱點j用i表示的話就是： j = 2 * id - i (重點理解)

 p[i] = (p[2 * id - i]) < (mx - i) ? (p[2 * id - i]) : (mx - i);

那麼上面這句程式碼可以理解為：我要計算的p[i]可以用已經計算過的p[j]（也就是p[2 * id - i])）計算；至於兩個值誰小等於誰的問題，接下來再討論。

 if (i < mx) {       p[i] = (p[2 * id - i]) < (mx - i) ? (p[2 * id - i]) : (mx - i);  } else {       p[i] = 1;  }

從上圖我們可以看出，條件i < mx，說明要求的迴文半徑p[i]可以使用對稱性求，得出的是p[j]和mx - i的最小值(此處下邊詳細解釋)。當i >= mx時，不能再使用對稱性求出，也就是說上一個迴文子串結束了，我們需要從1開始再計算一個新的迴文子串，如果它大於上一個迴文子串的長度，則就是答案。

詳細解釋：取p[j]和mx - i的最小值

一種如綠線的示意，以p[i]為迴文半徑的迴文子串的半徑小於mx - i，也就是說這個迴文子串沒超過mx，這種情況迴文半徑的取值就是p[j]；

一種如黃線所示，以p[i]為迴文半徑的迴文子串的半徑大於mx - i，也就是說這個迴文子串超過了mx，所以它的迴文半徑最短也是mx-i，還可能大於它。但是我們不管它，只計算沒超過mx的部分。

所以這兩種情況綜合之後，就是取p[j]和mx - i的最小值

重新開始一個新的子串：

while (s_new[i - p[i]] == s_new[i + p[i]] && i + p[i] < len && i - p[i] > -1) {            p[i]++;        }

重新選取mx和id：

if (mx < i + p[i])        {            id = i;            mx = i + p[i];        }

如果有子串比之前的串更長則更新：

if (max_len < p[i]) {       max_len = p[i];       c = i;   }

完整程式碼：