Cod sursa(job #406610)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 1 martie 2010 17:58:46
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<stdio.h>
#include<bitset>
using namespace std;

int sign[30],i,j,n,m,v[1003][1003];
char a[1003][1003],b[1003][1003];

bitset<1003> bun[1003];

int main()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	
	scanf("%d %d",&m,&n);
	
	for(i=1;i<=m;++i) scanf("%s",b[i]+1);
	
	for(i=1;i<=n;++i) 
	{
		scanf("%s",a[i]+1);
		for(j=1;j<=n;++j) sign[ int(a[i][j]-'a'+1) ]++;
	}
	
	for(char k='a';k<='z';++k)
		for(i=1;i<=m;++i)
			for(j=1;j<=m;++j) 
			{
				v[i][j]=v[i][j-1]+v[i-1][j]-v[i-1][j-1];
				if(b[i][j]==k) ++v[i][j];
				
				if(i>=n&&j>=n)
				{
					int nr=v[i][j]-v[i-n][j]-v[i][j-n]+v[i-n][j-n];
					if(nr!=sign[ int(k-'a'+1) ]) bun[i][j]=1;
				}
				
			}
	
	int rez=0;
	for(i=n;i<=m;++i)
		for(j=n;j<=m;++j) if(!bun[i][j]) rez++;
	
	printf("%d\n",rez);
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}