配点 : $500$ 点

問題文

0 と 1 からなる文字列 $S$ が与えられます。 以下の操作を好きな回数繰り返すことで $S$ の要素をすべて 0 にできるような、$|S|$ 以下の最大の整数 $K$ を求めてください。

• $S$ の長さ $K$ 以上の連続する区間 $[l,r]$ を選ぶ(すなわち、$r-l+1\geq K$ が満たされる必要がある)。$l\leq i\leq r$ なるすべての整数 $i$ に対し、$S_i$ が 0 なら $S_i$ を 1 に、$S_i$ が 1 なら $S_i$ を 0 に置き換える。

制約

• $1\leq |S|\leq 10^5$
• $S_i(1\leq i\leq N)$ は 0 または 1 である

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

操作を好きな回数繰り返すことで $S$ の要素をすべて 0 にできるような 最大の (21:08 JST 修正) 整数 $K$ を出力せよ。

010

2

以下の操作で、$S$ の要素をすべて 0 にできます。

• 長さ $3$ の区間 $[1,3]$ に操作を行う。$S$ は 101 になる。
• 長さ $2$ の区間 $[1,2]$ に操作を行う。$S$ は 011 になる。
• 長さ $2$ の区間 $[2,3]$ に操作を行う。$S$ は 000 になる。

100000000

8

00001111

4