Algorithm 演算法 - 最長回文子字串 馬拉車算法 Manacher's algorithm

簡介 Intro 以下取自維基百科 Manacher 於 1975 年發現了一種線性時間演算法，可以在列出給定字串中從任意位置開始的所有回文子串。並且，Apostolico, Breslauer & Galil 發現，同樣的演算法也可以在任意位置尋找全部極大回文子串，並且時間複雜度是線性的。因此，他們提供了一種時間複雜度為線性的最長回文子串解法。另外，Jeuring (1994), Gusfield (1997) 發現了基於字尾樹的演算法。也存在已知的高效並列演算法。 最長回文子串演算法(Lon...