!回文に関連する実装が苦手です。回文について考えなければならないときはいつも気が重かったのですが、与えられた文字列から回文となる部分文字列を列挙する方法を@nico_shindanninさんがニコニコ生放送で解説していらっしゃいました。分かりやすい解説だったので、メモとしてまとめました。次の文字列を考えてみます。先頭から5文字の部分文字列、CBABCは回文になっています。ナイーブなO(N3)を実装して確かめてみました。s[i:j+1]これはとても直感的な実装です。部分文字列を列挙し回文であるかどうかを調べています。この実装の動作を図示すると次のようになります。回文となる文字列の数は意外と多く、9個ありました。続いては@nico_shindanninさんが紹介していた方法です。回文の性質をうまく利用して、部分文字列の中央から広げて行くようにチェックを行うことによって計算量をO(N2)に落としています。1こちらの実装の動作を図示すると次のようになります。文字列の長さが10,000個の場合、O(N2)の実装は手持ちの端末で0.1秒以内に終わりますが、O(N3)の実装では10秒ほどかかりました。@nico_shindanninさんの放送のおかげで回文に対する苦手意識が少し和らぎました。これからは回文を使った問題も積極的に解いて行こうと思います。