#include<cstdio>
#include<iostream>
using namespace std;

//把每行计算成一整数，用kmp算法让每个星座进行行比较

char data[1000][1001],cons[100][50][51];
long long num,data2[1000],cons2[100][50];
int N,M,T,P,Q;
int kmp[100][50];
bool used[100];

int compute(){
	int ccount=0,i,j,k,l;
	for(l=0;l<T;l++){
		for(k=j=0;k<N&&j<P;k++)
			if(data2[k]==cons2[l][j])
				j++;
			else if(j)
				j=kmp[l][j-1]+1,k--;
		if(j==P) used[l]=true;
	}

	for(i=0;i<M-Q;i++){
		for(j=0;j<N;j++)
		{
			data2[j]<<=1;
			data2[j]&=num;
			if(data[j][i+Q]=='*')
				data2[j]++;
		}
		
		for(l=0;l<T;l++){
			if(used[l])
				continue;
			for(k=j=0;k<N&&j<P;k++)
				if(data2[k]==cons2[l][j])
					j++;
				else if(j)
					j=kmp[l][j-1]+1,k--;
			if(j==P) used[l]=true;
		}
	}
	for(i=0;i<T;i++)
		if(used[i]) ccount++;
	return ccount;
}

int main(){
	int ccount=1;
	while(scanf("%d%d%d%d%d",&N,&M,&T,&P,&Q)&&(N|M|T|P|Q)){
		int i,j,k;
		for(i=0;i<N;i++)
			for(scanf("%s",&data[i]),data2[i]=0,j=0;j<Q;j++)
			{
				data2[i]<<=1;
				if(data[i][j]=='*')
					data2[i]++;
			}
		for(i=0;i<T;i++){
			for(j=0;j<P;j++)
				for(scanf("%s",&cons[i][j]),cons2[i][j]=0,k=0;k<Q;k++)
				{
					cons2[i][j]<<=1;
					if(cons[i][j][k]=='*')
						cons2[i][j]++;
				}
			for(kmp[i][0]=-1,j=1;j<P;kmp[i][j++]=0);
			for(j=1;j<P;j++){
				for(k=kmp[i][j-1];k>=0&&!(cons2[i][k+1]==cons2[i][j]);k=kmp[i][k]);
				kmp[i][j]=(cons2[i][k+1]==cons2[i][j]?k+1:-1);
			}
		}
		if(P>N||Q>M){
			printf("Case %d: %d\n",ccount++,0);
			continue;
		}
		(num=(1<<Q))--;
		memset(used,0,sizeof(used));
		printf("Case %d: %d\n",ccount++,compute());
	}
	return 0;
}

• Re:哪位高手帮忙看一下啊，都wa到无语了…… (1836) xuanximei1212 2008-11-18 19:12:54