记录编号	37138	评测结果	AAAAAAAAAAWAA
题目名称	加利福尼亚旅店	最终得分	92
用户昵称	Czb。	是否通过	未通过
代码语言	C++	运行时间	0.112 s
提交时间	2012-03-26 07:29:20	内存使用	0.30 MiB

#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b

int n,l1,l2,ans,f[100][100];

char s[100],c[100];

int dp()
{
	int i,j,k,t;
	k=t=0;
	for(i=1;i<=l1;i++)
	{
		if(s[i-1]=='*')
		{
			for(j=1;j<i-k;j++)
			{
				f[i][j]=max(f[i-1][j],f[i][j-1]);
			}
			for(j=i-k;j<=l2;j++)
			{
				f[i][j]=max(f[i][j-1],f[i-1][j]);
				f[i][j]=max(f[i][j],f[i-1][i-k-1]+j-(i-k-1));
			}
			k++;
		}
		else
		{
			for(j=1;j<=l2;j++)
			{
				if(s[i-1]=='?'||s[i-1]==c[j-1])
					f[i][j]=f[i-1][j-1]+1;
				else
				{
					f[i][j]=max(f[t][j-1],f[i][j-1]);
					if(f[t][j]<=i-k)
						f[i][j]=max(f[i][j],f[t][j]);
				}
			}
			t=i;
		}
	}
	if(l1-k>l2)return -1;
	return f[l1][l2];
}

int main()
{
	freopen("hotela.in","r",stdin);
	freopen("hotela.out","w",stdout);
	while(scanf("%s\n",s)==1)
	{
		ans=0;
		scanf("%d\n",&n);
		l1=strlen(s);
		while(n--)
		{
			scanf("%s\n",c);
			l2=strlen(c);
			memset(f,0,sizeof(f));
			if(dp()==l2)
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}