시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 188 | 58 | 52 | 33.548% |
JOI (日本情報オリンピック) の本選に向けてプログラミングの練習をしていたあなたは,今年度の JOI の予選の問題には数値を扱う問題ばかりが出題され,文字列を扱う問題がなかったことに気がついた.そこであなたは,こっそり文字列の問題に強くなってライバルたちに差をつけることにした.
JOI の過去問を眺めていると,J
, O
, I
の 3 種類の文字からなる文字列に慣れておく必要がありそうなことがわかった.そこで,そのような文字列について考えよう.あなたは「与えられた文字列が JOI という部分文字列をもつかどうかを答えよ」という問題を思いついたものの,これはすぐに解けてしまった.もっとレベルの高い問題を解きたいあなたは,以下のような問題を作った.
文字列 t が文字列 s の部分文字列であるとは,t の先頭および末尾に何文字か (0 文字でもよい) を付け足すと s になることである.たとえば,JJOOII
は OJJOOIIOJOI
の部分文字列である.一方,JOI
は JOOI
の部分文字列ではない.
また,0 以上の整数 k に対し,レベル k の JOI 列とは,k 個の文字 J
,k 個の文字 O
,k 個の文字 I
をこの順に並べた文字列のことであるとする.たとえば,JJOOII
はレベル 2 の JOI 列である.
与えられた文字列の部分文字列である JOI 列のうち,レベルが最大のものを求めたい.
J
, O
, I
の 3 種類の文字からなる長さ N の文字列 S が与えられたとき,レベル k の JOI 列が S の部分文字列であるような最大の k の値を求めるプログラムを作成せよ.
標準入力から以下のデータを読み込め.
J
, O
, I
の 3 種類の文字からなる文字列 S が書かれている.標準出力に,レベル k の JOI 列が S の部分文字列であるような最大の k の値を表す整数を 1 行で出力せよ.
OJJOOIIOJOI
2
OJJOOIIOJOI
はレベル 2 の JOI 列である JJOOII
を部分文字列として含んでおり,レベル 3 以上の JOI 列は部分文字列として含まない.
IJJIIJJJ
0
レベル 0 の JOI 列は長さ 0 の文字列である.
JOIJOIJOIJOIJOI
1
OOJJJJJJJOOOOIIIII
4