← 返回题目列表

AtCoder · joi2012ho1

A. JJOOII模式

中文机器翻译题面 查看原题

配点: 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