有什麼淺顯易懂的Manacher Algorithm講解？

01-11

刷leetcode的時候遇到的關於palindrome的題，要用manacher演算法來解。但是google了一下manacher的講解發現都很難理解，不知道有沒有什麼直觀點的方法來理解這個演算法？

_(:з」∠)_量化分析的話可以搜索到的教程大概都會比我說的嚴謹與清楚許多，所以就說一下Manacher Algorithm的最主要的思想吧。。

為了方便地處理奇、偶迴文串判別條件的區別，我們先將原串中所有字元之間增添一個原串中不曾出現的字元（我們假定為「#」）。

譬如說，abaaba，在增添後就變成了 #a#b#a#a#b#a，

這樣，以#為中心的迴文串，在原串中就是偶迴文串。

然後，我們再規定兩個數組與幾個變數的意義:

數組Ma[i]：代表添加了「#」後的字元串。

數組Mp[i]：代表以字元串第i位為中心的迴文串的最大長度。

變數Mx ：代表當前「已經匹配完畢的結尾最遠的迴文串」到達了Ma[]數組的第Mx位。

變數ID ：代表當前「已經匹配完畢的結尾最遠的迴文串」中心為Ma[]數組的第ID為。

不難發現，p[i]-1即是該迴文串的長度……

在此……借用一下 @鄺斌菊苣的模板中的C++代碼來進行演算法說明。

我們來逐行看。

16行就不必說啦！

第17行，循環變數i代表了當前正在判斷Ma串的第i位為中心的迴文子串最長長度。

第十八行，是整個演算法最核心的部分，也是O(n)時間複雜度的保障。

我們考慮到，假如當前的i已經被包含在曾經被判斷過的迴文串內（即Mx&>i)，那麼它在這個迴文串中相對應的那個字元Ma[2*ID-i]，應當已經被計算過以它為中心的迴文串可以有多長了。

那麼，我們以第i位為中心的迴文串長度，就有了第一個下限Mp[2*ID-i]。

但是，我們考慮到，以Ma[2*ID-i]為中心的迴文串，它可能延展到了以Ma[ID]為中心的迴文串之外。。這樣我們就不能保證以Ma[i]為中心的迴文串包括了以Ma[ID]為中心的迴文串之外的部分。

所以我門得到了第二個下限Mx-i

綜上，在Mx&>i時，我們就得到了Mp[i]=min(Mp[2*id-i],mx-i);

第19行，考慮到第18行我們只得到了一個可憐的下限（……

我們要在這個下限的基礎上繼續向外擴展。

（畫外音：教練，這個暴力匹配怎麼保證複雜度還是O(n)呢！Σ( ° △ °|||)︴）

對於這一步的演算法複雜度分析，我們可以分為三種情況！

考慮當前這一位i，在第18行的位置所執行的操作

①Mp[i]=1，說明Mx沒有覆蓋超過i，那麼Mx的値在這一步執行後一定會增加。

②Mp[i]=Mx-i，說明以Ma[i]為中心的迴文串至少到達了Mx，那麼Mx的値在這之後不會減少。

③Mp[i]=Mp[ID*2-i]，說明可憐的Ma[i]只有這麼長已經匹配不出去了。。T_T

考慮到，Mx的値是單調的，並且始終不會超過字元串長度Len，那麼對於所有的i，①、②種情況的執行時間總和不會超過Len。因此總時間複雜度依舊是O(n)。

第二十行，更新Mx和ID的値。。

-------------------------

大概就想到這麼多啦[&>/&<].....比較懶就不附圖片了。。感覺按照這個自己寫一個栗子算一算就明白了！。。

如果有哪個地方一不小心忽略過去了或者有哪個地方沒有講明白……隨時等待改進w

https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/