No.2606 Mirror Relay
タグ : / 解いたユーザー数 31
作問者 : 👑
amentorimaru
/ テスター :
👑 
seekworser
問題文
とある仮想空間では一人称視点で過ごしますが、鏡の前では自分がどんな姿であるか確認することができるため、多くの人の溜まり場になっています。
エトワーニュくんはそんな鏡にちなんで回文をたくさん見つけるリレーをする遊びを提案しました。
英小文字列 $S$ が与えられます。
さらに空の文字列 $X$ が与えられた上で次の操作を好きなだけ繰り返すことができます。はじめ、スコアは $0$ です。
- $X$ の末尾に好きな英小文字を一文字加え、次の通りにスコアが計算される
- $X$ が回文でない場合、スコアは変動しない
- $X$ が回文である場合、 $S$ に存在する $X$ の個数を $Y$ とした時に $|X|\times Y$ が加点される
このリレーで得られるスコアの最大値を求めてください。
なお $S$ に存在する $X$ の個数は、区間の重複を許して数えるものとします。
厳密には $i=1,2,\dots ,|S|-|X|+1$ に対して、 $S$ の $i$ 文字目から $i+|X|-1$ 文字目の連続部分文字列が $X$ と等しくなる $i$ の個数として定義します。
入力
$S$
- $S$ は英小文字列
- $1\le |S| \le 2\times 10^5$
出力
答えを出力せよ。
サンプル
サンプル1
入力
baabaabaacaa
出力
34
開始からaabaabaaの順に末尾に繋げると $1\times 8 + 2\times 4 + 0+0+5\times 2 + 0+0+8\times 1=34$ で最も高いスコアとなります。
例えばaaが作成された際に、 $|X|=2$ であり、 $Y=4 (i=2,5,8,11)$ であるため、 $2 \times 4 = 8$ が加算されます。
他にもaabaaが作成された際に、 $|X|=5$ であり、 $Y=2(i=2,5)$ であるため、 $5 \times 2 = 10$ が加算されます。この二つは真ん中のaaが重なっていますが、重ねて数えてよいものとします。
aabaabは回文でないため、加点がされていません。
このほかにもbaabaabの順に末尾を繋げると $1\times 3+0+0+4\times 2+0+0+7\times 1 = 18$となりますが、最も高いスコアではありません。
サンプル2
入力
abc
出力
1
サンプル3
入力
zzzzabcddcba
出力
20
サンプル4
入力
disablepixellightsmirrorresolutionturnoffmirrorocclusionreflectlayersmaximumantialiasing
出力
21
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。