配点: 100 点
您在为 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 的值。
制限
| 1 \leqq N \leqq 1000000 \,(= 10^6) | S 长度 |
入力
从标准输入读取以下数据。 由
- 1 在线
写在方格
J,O,I的 3 类型的字符组成的字符串 S 。
出力
标准输出,电平 表示 k 的 JOI 列是 最大的是 S 的子串 编写一个程序来查找 k 值的整数 输出为 1 行。
採点基準
评分数据中,分配的分数 20 对于%,N \leqq 100 满意。 是
入力例 1
OJJOOIIOJOI
出力例 1
2
OJJOOIIOJOI 是级别
这是 2 的 JOI 列
包含 JJOOII 作为子字符串,
水平 3 以上的 JOI 序列不作为子字符串包含在内。
入力例 2
IJJIIJJJ
出力例 2
0
等级 0 的 JOI 列长度 它是一个 0 字符串。
入力例 3
JOIJOIJOIJOIJOI
出力例 3
1
入力例 4
OOJJJJJJJOOOOIIIII
出力例 4
4