問題一覧 > 通常問題

No.2606 Mirror Relay

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : 👑 amentorimaruamentorimaru / テスター : 👑 seekworserseekworser
2 ProblemId : 10280 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-13 09:25:59

問題文

とある仮想空間では一人称視点で過ごしますが、鏡の前では自分がどんな姿であるか確認することができるため、多くの人の溜まり場になっています。

エトワーニュくんはそんな鏡にちなんで回文をたくさん見つけるリレーをする遊びを提案しました。


英小文字列 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。