Skip to content →

部分文字列に含まれる回文の種類数の上限

Sに部分文字列として含まれる回文の種類数は |S| 個以下である。
証明 : Tに一文字追加した S=’c’+T に a, b (a < b) を中心とする2つの回文が増えたとする。S[x] = S[2a-x], S[x] = S[2b-x] より S[x]=S[±2(b-a)+x] である。従って、S[:2a] = S[2(b-a):2b] だから、a を中心とする回文が増えたことに反する。従って文字列長が一つ増えるたびに、高々一つしか含まれる回分の種類は増加しない。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA