Manacher的算法
為了線上性時間內找到字元串中最長的回文，算法可以利用以下關於回文和子回文的特徵或觀察：
回文的左側是其右側的鏡像。
（案例1）如果第二回文位於第一回文的範圍內，則其中心位於第一回文的右側內的第三回文將具有與錨定在左側鏡中心的第二回文的長度完全相同的長度。第一個回文至少有一個字元（不符合第一個回文的左邊界）。
（案例2）如果第二回文符合或延伸超出第一回文的左邊界，那么從第二回文的中心到第一回文的左邊界的距離恰好等於距第三回文的中心的距離回文到第一回文的右邊界。
為了在案例2下找到第三回文的長度，然後將第一回文的右外側字元後面的下一個字元與其關於第三回文中心的鏡像字元進行比較，直到沒有匹配或沒有更多字元為止。
（案例3）第一和第二回文都沒有提供信息來幫助確定第四回文的回文長度，第四回文的中心位於第一回文的右側之外。
因此，當從左到右確定弦中子串的回文長度時，需要將回文作為參考（即，第一回文的作用），其具有字元串中最右側的字元（因此，病例2中的第三個迴文結構和病例3中的第四個迴文結構可以取代第一個迴文結構成為新的參考文獻 ）。
關於字元串中每個字元的回文長度確定的時間複雜度：案例1沒有字元比較，而對於案例2和3，只有參考回文右邊最外面字元串中的字元才是比較的候選者（因此案例3總是產生新的參考回文，而案例2隻在第三回文實際上長於其保證的最小長度時才這樣做。
對於偶數長度的回文，中心位於中間兩個字元的邊界。
執行
一串N個字元。s2是s的派生字元串，包括N * 2 + 1個元素，每個元素對應於下列之一：s中的N個字元，字元中的N-1個邊界，以及第一個和最後一個之前和之後的邊界性格分別。
對於回文長度確定中的元素匹配，s2中的邊界等於s2中的任何其他邊界。
p是s2中每個元素的回文跨度的數組，從中心到最外層元素，其中每個邊界朝向回文的長度計數（例如，三個元素長的回文跨度為1的回文跨度）。
c是當前已知包含最接近s2右端的邊界的回文中心的位置（即，回文的長度= p [c] * 2 + 1）。
r是該回文最右邊界的位置（即r = c + p [c]）。
我是s2中一個元素（即一個字元或邊界）的位置，其回文跨度正在確定，我總是在c的右邊。
i2是c周圍的i的鏡像位置（例如，{i，i2} = {6,4}，{7,3}，{8,2}，...當c = 5時。
