#3725. PA2014 Final Matryca

内存限制:128 MiB 时间限制:5 Sec

题目描述

有一堵长度为n的墙需要刷漆,你有一把长度为k的刷子。墙和刷子都被均匀划分成单位长度的小格,刷子的每一格中都沾有某种颜色(纯色)的漆。你需要用这把刷子在墙上每一个可能的位置(只要刷子不超出墙,且对准格子;共有n-k+1个位置)都刷一遍。如果墙上的某一格被不同颜色的漆刷过,那么它会呈现混合色。

现在墙上某些格子需要刷成给定的颜色。求出能够完成任务的最短的刷子长度k。

输入格式

输入为一个长度为n(1<=n<=1000000)的字符串,由大写字母和星号组成。大写字母表示某种纯色,星号表示此位置颜色不作要求。

输出格式

输出最小的k。

样例

样例输入


			
A*B*B*A

样例输出


			
6

数据范围与提示

解释:

刷子的颜色为ABBBBA。