Manacher
説明
ある文字列 $S$ が与えられているとする。Manacher では, それぞれの $i$ について文字 $i$ を中心とする最長回文の半径を記録した配列を線形時間で構築するアルゴリズムである。
具体例を以下に示す。例えば $i = 6$ を中心とする最長回文は "aba" つまり $2$ である。
abaaababa
121412321計算量
$O(|S|)$
実装例
Manacharよりも Manachan の方が可愛いので Manachan にしてあります(?)