九度OJ最短摘要的生成

使用滑动窗口的思想来获取最短摘要，可以达到O（N）的时间复杂度。

http://ac.jobdu.com/problem.php?id=1397

#include <stdio.h>
#include <string.h>
#include <memory.h>

#define MAX 100010
char s[100010],p[100010];
int hash[10],movewindow[10],len1,len2,minlen;
int num;         //滑动窗口中*的个数

bool IsAllExisted()       //判断滑动窗口中是否包含所有的关键字
{
	int i,temp=0;
	for(i=0;i<10;i++)
	{
		if(hash[i]>movewindow[i])    //统计滑动窗口中包含摘要字符的个数小于摘要中对应字符的个数
			temp+=hash[i]-movewindow[i];
	}
	if(num>=temp)        //缺少的字符使用*来代替
		return true;
	else
		return false;
}

int GetMinAbstract()          //取得最短摘要
{
	int i,start=0,end=len2-1;
	minlen=MAX;
	num=0;
	for(i=start;i<end;i++)   //初始化滑动窗口
	{
		if(s[i]=='*')
			num++;
		else
			movewindow[s[i]-'0']++;
	}

	while(start<=end && end<len1)
	{
		if(s[end]=='*')
			num++;
		else
			movewindow[s[end]-'0']++;
		while(IsAllExisted())
		{
			if(end-start+1<minlen)
				minlen=end-start+1;
			if(s[start]=='*')
				num--;
			else
				movewindow[s[start]-'0']--;
			start++;   //滑动窗口中包含摘要的时候，左边界向后移动，滑动窗口变小
		}
		//while循环退出的时候，滑动窗口中不包含摘要，此时右边界向后移动，滑动窗口变大
		end++;
	}
	return minlen;
}
int main(void)
{
	int i,n;
	while(scanf("%s %s",s,p)!=EOF)
	{
		len1=strlen(s);
		len2=strlen(p);
		memset(hash,0,sizeof(hash));
		memset(movewindow,0,sizeof(movewindow));

		for(i=0;i<len2;i++)
			hash[p[i]-'0']++;    //统计每个关键字出现的次数

		n=GetMinAbstract();
		if(n==MAX)
			printf("0\n");
		else
			printf("%d\n",n);
	}
	return 0;
}

如果使用二分搜索的思想可以达到O（N*lgN）的时间复杂度。