Cod sursa(job #580213)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 12 aprilie 2011 20:29:51
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>


int m,n,i,j,k,x[1001][1001][30],a[30],rez;

bool ok;

char y[1001];


int main()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%d%d\n",&m,&n);
	for(i=1;i<=m;++i)
	{			
		gets(y);
		for(j=0;j<m;j++)	
		{
			for(k='a';k<='z';++k)
				x[i][j+1][k-'a']=x[i-1][j+1][k-'a']+x[i][j][k-'a']-x[i-1][j][k-'a'];
			x[i][j+1][y[j]-'a']++;
		}
	}
	for(i=1;i<=n;++i)
	{
		gets(y);
		for(j=0;j<n;j++)	
		{
			++a[y[j]-'a'];
		}
	}
	for(i=n;i<=m;++i)
		for(j=n;j<=m;++j)	
		{
			ok=true;
			for(k='a';k<='z';++k)
			{
				if (x[i][j][k-'a']-x[i][j-n][k-'a']-x[i-n][j][k-'a']+x[i-n][j-n][k-'a']!=a[k-'a'])
				{
					ok=false;
					break;
				}
			}
			if (ok) ++rez;
		}
	printf("%d",rez);
}