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

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

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

Output
输出最小的k。

Sample Input
ABB*A
Sample Output
6
HINT
解释:

刷子的颜色为ABBBBA。

solution:

这道题还主要是一个大胆猜测题。

发现

于是就 O ( n ) O(n) O(n)找出 x x x就行了。

这里还要注意:

  • 刚开始的tmp不能直接给成 s [ 0 ] s[0] s[0],因为 s [ 0 ] s[0] s[0]不一定有颜色要求,要先给成一个不可能出现的字符。

  • 不要习惯了把last和tmp都开始char(笑哭,也就只有我会犯这种zz错误)

  • ans要给成n,因为n就是刷子最长可能的数了

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
char s[1000005];
int main()
{
	scanf("%s",s);
	int n=strlen(s);
	char tmp='$';
        int last=0;
	int ans=n;
	for(int i=0;i<n;i++) 
	{
		if(s[i]!='*')
		{
			if(tmp=='$')
			{
				tmp=s[i];
				last=i;
			}
			else
			{
				if(s[i]!=tmp)
				{
					ans=min(ans,i-last);
					tmp=s[i];
					last=i;
				}
				else
				{
					last=i;
				}
			}
		}
	}
	printf("%d\n",n-ans+1);
	return 0;
}