Manacher 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /manacher#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /manacher#noredirect を利用してください。
name
Manacher 法
short description
Manacher 法とは、与えられた文字列 $S$ に対して、そのすべての位置 $i$ (ただし $0 \le i \lt \vert S \vert$) について「$S$ における $i$ 番目の文字を中心とする最長の回文の半径」をまとめて $O(\vert S \vert)$ で求めるアルゴリズムのひとつ。そのままでは奇数長の回文についてのみしか求まらない。偶数長の回文についても求めたいときは、$S$ の各文字の間にダミーの文字列を計 $\vert S \vert - 1$ 個挿入してできる文字列 $S'$ に対してもう一度 Manacher 法をすることになる。
input
文字列 $S$
output
すべての $i$ について、$S$ における $i$ 番目の文字を中心とする最長の回文の半径
time complexity
$O(\vert S \vert)$

参考文献

外部リンク