No.238

先頭から $k$ 文字目と末尾から $k$ 文字目が違う文字となる $k$ を求める.

そういう文字が1文字もないならばすでに回文なので, 文字数が奇数なら中央の文字を隣にコピーして増やし, 文字数が偶数なら適当な文字を中央に追加する.

$k$ が求まった場合, 先頭から $k$ 文字目〜末尾から $k$ 文字目の文字列 $t$ を考え, $t$ の先頭に $t$ の末尾の文字を追加した場合と $t$ の末尾に $t$ の先頭の文字を追加した場合それぞれで回文が作れるかどうかを調べる.