Cod sursa(job #41120)

Utilizator DorinOltean Dorin Dorin Data 27 martie 2007 23:00:20
Problema Matrix Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
# include <stdio.h>

# define input "matrix.in"
# define output "matrix.out"

# define max 1001

long a[max][max],b,i,j,n,m,rez,d[28],y[28];
char c,x[max][max];

int verifica(int i,int j)
{
	int ii,jj;
	for(ii = 1;ii<=27;ii++)
		d[ii] = 0;
	for(ii = 0;ii<m;ii++)
		for(jj=0;jj<m;jj++)
			d[x[ii+i][jj+j] - 'a'+1]++;
	int ok=1;
	for(ii = 1;ii<=27;ii++)
		if(d[ii] != y[ii])
		{
			ok = 0;
			break;
		}
	return ok;
}

int main()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);

	scanf("%ld%ld",&n,&m);

	for(i=1;i<=n;++i)
	{
		scanf("%c");
		x[i][0] = ':';
		for(j=1;j<=n;++j)
		{
			scanf("%c",&c);
			x[i][j] = c;
			a[i][j] =a[i-1][j]+a[i][j-1]-a[i-1][j-1]+c-'a'+1;
		}
	}
	for(i=1;i<=m;++i)
	{
		scanf("%c");
		for(j=1;j<=m;++j)
		{
			scanf("%c",&c);
			y[c-'a'+1]++;
			b+=c-'a'+1;
		}
	}

	for(i=m;i<=n;++i)
		for(j=m;j<=n;++j)
			if(a[i][j] - a[i-m][j]-a[i][j-m]+a[i-m][j-m] == b)
			{
				if(verifica(i-m+1,j-m+1))
					rez++;
			}

	printf("%ld",rez);

	return 0;
}