はじめに
長さ N の文字列 S を考えます
S の空でない部分文字列 (N(N - 1)/2 通りあります) のうち, 回文であるようなものは高々 N 種類しか存在しない
らしいです
N を達成するのは簡単で, 全部違う文字にすればいいです
けどここから増やす方法は存在しないのでしょうか？
なかなかに非直感的に感じたのでちゃんと考えてみましょう
本文
帰納的に示すのがよさげです
文字列 S が存在していて, S の末尾に文字 c を一文字追加するときのことを考えます
この時, S に含まれる回文の種類数は高々 1 種類しか増えないことが言えます
さて, このときの回文の増え方として c が回文の右端になる という場合のみ考えればいいことがわかります
そのような回文のうち, 最も直径が長いものを T, そうでないもののうちの一つを U とすると, T, U は回文なので T に U が二つ以上含まれることがわかります (右端に合わせるか左端に合わせるか)
よって, T 以外の回文はすべて S にすでに存在していたことになります
したがって, S の長さが 1 増えるたび回文は高々 1 種類しか増えないことがわかります
以上より, S の空でない部分文字列のうち, 回文であるようなものは高々 |S| 種類しか存在しないことがわかりました
おわりに
こう考えるとわりと単純 けどぱっとは思いつかなくない？
と思い記事を書いてみました
回文に関するデ/アといえばみんな大好き Manacher's algorithm のほかに Palindromic Tree というものがあるらしいですね 勉強しないとな
