比赛 20120323 评测结果 AAAAAAAAAAAAAAA
题目名称 加利福尼亚旅店 最终得分 100
用户昵称 恢复用户700 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2012-03-23 21:39:52
显示代码纯文本
(*
Problem		:	Hotel
Author		:	whitetooth
Start Time	:	2012-3-23 19:21
Finish Time	:	2012-3-23 19:49
Result		:	
Method		:	Dynamic Programming
*)
Program Hotel;
Const
	maxn=50+5;
Var
	f,vis						:array[0..maxn,0..maxn] of boolean;
	s1,s2						:string;
	n,i							:longint;
	ans							:longint;
	
Procedure Dfs(p,q,l1,l2:longint);
Begin
	if vis[p,q] then exit;
	vis[p,q]:=true;
	
	if (p>l1)and(q>l2) then
		begin
			f[p,q]:=true;
			exit;
		end;
		
	if (p>l1)and(q<=l2) then
		begin
			f[p,q]:=false;
			exit;
		end;
	if (p<=l1)and(q>l2) then
		begin
			if s1[p]='*' then
				begin
					dfs(p+1,q,l1,l2);
					f[p,q]:=f[p+1,q];
				end
			else f[p,q]:=false;
			exit;
		end;
	
	if s1[p]='?' then
		begin
			dfs(p+1,q+1,l1,l2);
			f[p,q]:=f[p+1,q+1];
			exit;
		end;
		
	if s1[p]='*' then
		begin
			dfs(p,q+1,l1,l2);
			dfs(p+1,q,l1,l2);
			f[p,q]:=f[p,q+1] or f[p+1,q];
			exit;
		end;
		
	if s1[p]<>s2[q] then f[p,q]:=false
	else
		begin
			dfs(p+1,q+1,l1,l2);
			f[p,q]:=f[p+1,q+1];
		end;
End;
	
Procedure Main;
Begin
	ans:=0;
	
	readln(s1);
	readln(n);
	for i:=1 to n do
		begin
			readln(s2);
			fillchar(vis,sizeof(vis),false);
			dfs(1,1,length(s1),length(s2));
			if f[1,1] then inc(ans);
		end;
		
	writeln(ans);
End;
	
Begin
	Assign(input,'hotela.in'); reset(input);
	Assign(output,'hotela.out'); rewrite(output);
	While not seekeof do main;
	Close(input); close(output);
End.