# 馬拉車算法 (Manacher's Algorithm)

**原文: https://medium.com/hoskiss-stand/manacher-299cf75db97e**

**此篇文章非本人撰寫，只做個人筆記之用，非營利性質**

來看一個[問題](https://leetcode.com/problems/longest-palindromic-substring/)，找出一個字串中，包含的最長迴文字串 (Longest Palindromic Substring)，例如給定字串 cbabed，要找的結果是 bab。最直覺的[暴力法跟動態規劃](https://algorithm.yuanbin.me/zh-tw/string/longest_palindromic_substring.html)，計算速度都比不上這個 manacher’s algorithm，分析問題的方式值得好好地推敲一番。網路上介紹的文章不少，但適合自己消化的卻不多，這篇筆記主要參考詳細的 [geeksforgeeks](https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/)，再試圖整理搭配圖例以更好理解。

_寫下這篇，也為了想講句自我激勵的幹話: 有時候，當你耗費大量的時間也無法輕易掌握一項知識時，除了耍廢跟人生好難以外，永遠要相信有一種可能，是還沒有找到適合自己閱讀的教學說明…QQ_


奇數迴文字串

首先我們對字串間隔插入一個原本不會出現的符號，程式實作用 #，這邊的圖用 _ 表示。如此一來對於每一個位置，我們可以算出一個值 LPS length，這個值表示以這個位置為中心，到達最長迴文字母的半徑。以上面這張圖為例，看到中間的紅色虛線，以 a 的位置為中心點，左右對稱的迴文完整是 \_a\_b\_a\_b\_a\_，而從 a 到左右邊界的長度就是 5。而我們再仔細觀察，這個值也會等於原本的字串(拿掉多加的符號)中，每個字為中心找到的 Longest Palindromic Substring 長度，以紅色虛線 a 而言就是 ababa ，長度也是 5。


偶數迴文字串

所以如果我們可以算出所有的 LPS length，也知道中心點的位置，我們就可以得到問題所要找的最大 LPS。而加入符號有個好處就是，當迴文字串長度是偶數的時候，中心點會落在符號上，不需特別處理較為簡便。例如上圖的中心為中間虛線 _，LPS length 為 6。

那我們要如何更快速地得到所有的 LPS length ? 關鍵就是好好利用迴文的性質。請參考下圖觀察一下，首先我們知道一般處理陣列是由左至右的順序，這邊也是相同，依序算出每個位置的 LPS length。那假設我們現在已經要計算 current right 位置的 LPS length，然後這個位置左邊以前的值已經都知道了，而且符合以下這樣的狀況：


current right 的左邊有個 center (灰色虛線)，以這個 center 為中心，LPS 的覆蓋範圍是從 center\_left 到 center\_right，而這個 center 對應到的 center\_right 是目前最大(最右邊)的，同時也表示 center\_left 到 center，對於 center\_right 到 center，是完全對稱的。而 current\_right 對於 center 的另一邊，有個對稱點 current\_left，且 current\_left 的 LPS 範圍(左邊的三條藍色直線)，被涵蓋在 center\_left 到 center 裡面，依照計算順序 current\_left 的 LPS length 已經得知。這個時候我們知道 current\_left 的 LBS 外面那兩格 (左邊灰色三角形跟菱形) 一定不相等，否則 current\_left 的 LBS 就會更長，而且這些值對於 center 的右邊是完全對稱，(可以想成 center 就是一面鏡子，左邊的值”對折”就是右邊的值，所以這邊框框塗成對稱的顏色)。在這樣的情況下，我們可以直接得到 center\_right 的 LPS length 等於 center\_left 的 LPS length，也就是圖下方的第一行式子，不用再多加計算。而 current\_left 的 LPS 範圍被包含在 center\_left 到 center 裡面的情況，就等價於第二行式子，所以兩個條件結合可以得到第三個式子，先記下這個結論，這裡是理解程式碼中重要的一步。圖例這個情況也是[原文](https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/)提到的 case 1。


接著我們繼續探討其他狀況，如果 current_left 的 LPS 範圍**剛剛好**被 center\_left 包含呢？請看上圖，也就是 current\_left LPS 的最左邊字母，跟 center\_left 重疊，這時候我們可以確定左邊灰色三角形位置的值不會等於菱形位置的值，但以 center 為中心的對稱範圍，我們不能肯定 center\_right 再右邊一個的問號位置是什麼值，除非 center\_right 已經是字串的最後一個字，這種情況下我們可以肯定 current\_right 的 LPS length 等於 current\_left 的 LPS length，也就是原文的 case 2 狀況。那如果 center\_right 不是最後一個字，current\_right 的 LPS length 是有可能大於 current\_left 的 LPS length，也就是原文的 case 3 狀況 (建議搭配[原文例子](https://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-2/)搜尋 case 3 會更有概念)。而同樣的，我們可以得到圖下方第三行的結論，current\_right 的 LPS length 會大於等於，current\_left 的 LPS length 與 center\_right - current\_right 兩者中較小的值。


我們再看一種狀況，如果 current\_left 的 LPS 很長，長到超出 center\_left 的範圍如上圖。這時候可以先確定根據 current\_left 為對稱中心，左邊的兩格藍色位置是相等的，而且根據 center 對稱到右邊的藍色，也就是灰色菱形位置。但是在 center\_right 的再右邊一格灰色三角位置，這個值一定不會等於藍色位置的值，否則 center\_right 跟 center\_left 就會往外擴張，所以 current\_right 的 LPS length 被限制在 center\_right - current\_right 的長度。同樣可以得到圖下方第三行的結論。另外在思考過程中也畫了當 current\_left 的 LPS 右邊超過 center 的狀況，請見下圖


基本上跟上圖的情況跟結論是一樣的，概念就是 center 保證了 center\_left 到 center，center 到 center\_right 這兩者的對稱，但如果 center\_right 再右邊一格灰色三角位置，如果也對於 current\_right 是對稱，那 center\_right 就會擴張而不符合假設，所以 current\_right 的 LPS length 被壓在 center\_right -current\_right 。這也是原文的 case 4，不過原文寫到 LPS\[current\_right\] ≥ center\_right - current_right，我還想不明白怎樣會出現大於的情形，這是閱讀原文時有疑慮的地方，雖然對程式的實作處理影響不大。

根據以上幾種情況可以歸納出，當 center\_right 的範圍包含 current\_right 的時候，我們要求的 LPS length 都會大於等於一個下界限，甚至大部分狀況是等於： LPS\[current\_right\] ≥ min( LPS\[current\_left\], center\_right - current\_right)，再根據這個界限去計算實際的長度。另外就是依序計算的過程中，如果 current\_right 算出來的 LPS 範圍超過 center\_right，就要更新 center 還有 center\_right，維持 center 對應到的 center\_right 是目前最大(最右邊)的範圍。

可參考程式碼如下，若掌握上述迴文的性質，基本上程式碼應可以較容易理解。另外這個演算法的時間複雜度是 O(n)，雖然看起來 for 迴圈中還有個 while 迴圈，比較直接的想法是，只有當 case 3 的情況，current\_right 的 LPS 範圍有可能超過下界限時，while 的條件才會成立需要計算，其他都是看條件給值的 O(1) 情況。而且當計算新的 LPS 範圍時，就等於計算下一個 center 的 center\_right 範圍，而使得這個範圍內，case 3 情況以外的計算量又都是線性的，所以整體是 O(n)，更嚴謹的解釋或證明還是參考網路其他文章比較合適。

因為花了不少時間了解這個演算法，發現把圖畫一畫後，對於自己思考的內容會比較清晰，感謝網路上的資源讓我能從傻眼到理解，希望這個過程的筆記，有機會能讓人減少一些掌握的時間。如果有任何回饋或指點都非常歡迎，喜歡這篇的話也可以拍拍手按個讚，讓我知道這條路上總有夥伴 XD，謝謝～