suu_0313 https://blog.hatena.ne.jp/suu_0313/ Suuさんのブログ https://suu-0313.hatenablog.com/ はじめに 長さ N の文字列 S を考えます S の空でない部分文字列 (N(N - 1)/2 通りあります) のうち, 回文であるようなものは高々 N 種類しか存在しない らしいです N を達成するのは簡単で, 全部違う文字にすればいいです けどここから増やす方法は存在しないのでしょうか？ なかなかに非直感的に感じたのでちゃんと考えてみましょう 本文 帰納的に示すのがよさげです 文字列 S が存在していて, S の末尾に文字 c を一文字追加するときのことを考えます この時, S に含まれる回文の種類数は高々 1 種類しか増えないことが言えます さて, このときの回文の増え方として c が回… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsuu-0313.hatenablog.com%2Fentry%2F2023%2F02%2F24%2F135305" title="文字列に含まれる回文の種類数は高々 |S| 種類 - Suuさんのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2023-02-24 13:53:05 rich https://suu-0313.hatenablog.com/entry/2023/02/24/135305 1.0 100%