Manacher’s Algorithm (Manacher 的唸法
/ˈmænəkər/)，用是來尋找字串中最長回文子串 (Longest Palindromic Substring)的最好解法，時間複雜度可優化到了 O(n)。 由於算是是常考題，就花些時間了解一下吧。
最長回文子串 (Longest Palindromic Substring) 是常考題。Palindrome 就是順讀逆讀，字母都一樣的詞語，比如範例給的 「 bab 」、 「 bb 」 等等，實際單字如 「 level 」 也是一個的 Palindromic 單字。
先熟悉「 Dynamic Programming - 2D matrix 」解和「 中心擴散法 (Expand Around Center) 」就好了，還有聽過最佳解 Manacher’s Algorithm，時間複雜度可優化到了 O(n)，之後再花其他篇幅去補充。