問題一覧 > 通常問題

No.2204 Palindrome Splitting (No Rearrangement ver.)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 92
作問者 : srjywrdnprktsrjywrdnprkt / テスター : 👑 seekworserseekworser
4 ProblemId : 9103 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-31 19:50:18

問題文

あなたは文字列$S$を持っています。$S$は英小文字のみからなります。
あなたは$S$を任意の位置で分割し、何個かの文字列$s_1,~s_2, \cdots,~ s_N$を作ります($N$は任意)。ただし、各$s_i$は回文でなければなりません。
$s_i$の長さの最小値を$X$とします。あなたは$X$をできるだけ大きくしようとしています。$X$の最大値を求めてください。

入力

$S$

入力は以下の制約を満たす。

  • $1\leq |S| \leq 5000$
  • $S$は英小文字のみからなる。

出力

$X$の最大値を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
aaababbaa
出力
2

aa aba bb aaのように分割すれば良いです。

サンプル2
入力
ababababa
出力
9

$S$自体が回文のこともあります。この場合は分割しないのが最適です。

サンプル3
入力
abcdefghijklmnopqrstuvwxyz
出力
1

英小文字1文字からなる文字列は回文であることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。