Problem11187--01游戏

11187: 01游戏

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

给你一个长度为 $n$ 的 01 串 $s$,你可以进行操作: 选择一个操作集合 $U⊆\{0,1,⋯,n\}$ (可以是空集),然后每次选择一个最大的 $x∈U$ 并将其从 $U$ 中删去,然后将 $s[1,x]$ 按位取反,将 $s[x+1,n]$ 翻转。
注意 $s[1,x]$ 和 $s[x+1,n]$ 都可以为空子串。 定义一个字符串 $s$ 的价值为其满足相邻位不同的最长子段长度, 现在要求你选择一个操作集合,最大化操作完成后字符串 $s$ 的价值,你只需要输出字符串的价值。

Input

给出一行字符串 $s$,只包含 0/1

Output

输出一行一个整数,表示答案。

Constraints

对于 $100\%$ 的数据 $n≤10^7$

Sample 1 Input

01111

Sample 1 Output

3
选取集合 $U=\{1,4,5\}$ 第一步 将 $[1,5]$ 取反,$[6,5]$ 空区间不合法,序列变为 $[1,0,0,0,0]$
第二步 将 $[1,4]$ 取反,$[5,5]$ 翻转,序列变为 $[0,1,1,1,0]$
第三步 将 $[1,1]$ 取反,$[2,5]$ 翻转,序列变为 $[1,0,1,1,1]$
可以发现 $[1,3]$ 为符合题目要求的子段,答案为 $3$。

Sample 2 Input

10001

Sample 2 Output

3

Sample 3 Input

10001011101000001001

Sample 3 Output

11

Source/Category