要說馬拉車算法，必須說說這道題，查找最長回文子串，馬拉車算法是其中一種解法，狠人話不多，直接往下看：
給你一個字元串 s，找到 s 中最長的回文子串。
這是一個奇妙的算法，是1957年一個叫Manacher的人發明的，是以叫<code>Manacher‘s Algorithm</code>,主要是用來查找一個字元串的最長回文子串，這個算法最大的貢獻是将時間複雜度提升到線性，前面我們說的動态規劃的時間複雜度為 O(n2)。
前面說的中心拓展法，中心可能是字元也可能是字元的間隙，這樣如果有 n 個字元，就有 <code>n+n+1</code> 個中心：
為了解決上面說的中心可能是間隙的問題，我們往每個字元間隙插入”<code>#</code>“,為了讓拓展結束邊界更加清晰，左邊的邊界插入”<code>^</code>“,右邊的邊界插入 "<code>$</code>":
<code>S</code> 表示插入"<code>#</code>","<code>^</code>","<code>$</code>"等符号之後的字元串，我們用一個數組<code>P</code>表示<code>S</code>中每一個字元能夠往兩邊拓展的長度:
比如 <code>P[8] = 3</code>，表示可以往兩邊分别拓展3個字元,也就是回文串的長度為 3，去掉 <code>#</code> 之後的字元串為<code>aca</code>：
<code>P[11]= 4</code>，表示可以往兩邊分别拓展4個字元，也就是回文串的長度為 4，去掉 <code>#</code> 之後的字元串為<code>caac</code>：
假設我們已經得知數組P，那麼我們怎麼得到回文串？
用 <code>P</code> 的下标 <code>index</code> ，減去<code>P[i]</code>（也就是回文串的長度），可以得到回文串開頭字元在拓展後的字元串 <code>S</code> 中的下标，除以2，就可以得到在原字元串中的下标了。
那麼現在的問題是：如何求解數組P[i]
其實,馬拉車算法的關鍵是：它充分利用了回文串的對稱性，用已有的結果來幫助計算後續的結果。
假設已經計算出字元索引位置 P 的最大回文串，左邊界是PL，右邊界是PR：
那麼當我們求因為一個位置 <code>i</code> 的時候，<code>i</code> 小于等于 PR,其實我們可以找到 <code>i</code> 關于 <code>P</code> 的對稱點 <code>j</code>:
那麼假設 j 為中心的最長回文串長度為 len，并且在 PL 到 P 的範圍内，則 i 為中心的最長回文串也是如此：
以 i 為中心的最長回文子串長度等于以 j 為中心的最長回文子串的長度
但是這裡有兩個問題：
前一個回文字元串P，是哪一個？
有哪些特殊情況？特殊情況怎麼處理？
(1) 前一個回文字元串 <code>P</code>，是指的前面計算出來的右邊界最靠右的回文串，因為這樣它最可能覆寫我們現在要計算的 i 為中心的索引，可以盡量重用之前的結果的對稱性。
也正因為如此，我們在計算的時候，需要不斷儲存更新 P 的中心和右邊界，用于每一次計算。
(2) 特殊情況其實就是目前 i 的最長回文字元串計算不能再利用 P 點的對稱，例如：
以 <code>i</code> 的回文串的右邊界超出了 <code>P</code> 的右邊界 PR:
這種情況的解決方案是：超過的部分，需要按照中心拓展法來一一拓展。
<code>i</code> 不在 以 <code>P</code> 為中心的回文串裡面，隻能按照中心拓展法來處理。
具體的代碼實作如下：
至于算法的複雜度，空間複雜度借助了大小為n的數組，為O(n)，而時間複雜度，看似是用了兩層循環，實則不是 O(n2)，而是 <code>O(n)</code>，因為絕大多數索引位置會直接利用前面的結果以及對稱性獲得結果，常數次就可以得到結果，而那些需要中心拓展的，是因為超出前面結果覆寫的範圍，才需要拓展，拓展所得的結果，有利于下一個索引位置的計算，是以拓展實際上較少。
【作者簡介】：
秦懷，公衆号【秦懷雜貨店】作者，技術之路不在一時，山高水長，縱使緩慢，馳而不息。個人寫作方向：<code>Java源碼解析</code>，<code>JDBC</code>，<code>Mybatis</code>，<code>Spring</code>，<code>redis</code>，<code>分布式</code>，<code>劍指Offer</code>，<code>LeetCode</code>等，認真寫好每一篇文章，不喜歡标題黨，不喜歡花裡胡哨，大多寫系列文章，不能保證我寫的都完全正确，但是我保證所寫的均經過實踐或者查找資料。遺漏或者錯誤之處，還望指正。
劍指Offer全部題解PDF
2020年我寫了什麼？
開源程式設計筆記