[ Manacher's algorithm ] Linear time Longest palindromic substring 線性最長回文子串

Manacher演算法是Z algorithm的變種，可以說是雙向的Z algorithm，複雜度也是\(\ord N\)
其Z function定義如下:
     Z(i)=以位置i為中心的最長回文半徑
但是這樣只能處理回文長度是奇數的子串，因此必須幫字串做一些修改

假設原來的字串是: "asdsasdsa"
修改後變成: "@#a#s#d#s#a#s#d#s#a#"
其中'@'及'#'為不同字元且皆未在原字串中出現過
其Z function陣列為: 0 1 2 1 2 1 6 1 2 1 10 1 2 1 6 1 2 1 2 1
則 最大的數字-1 (10-1=9)就是我們要的答案

這裡提供Manacher algorithm產生Z function陣列的實作: