Cod sursa(job #498265)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 4 noiembrie 2010 19:00:18
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#define nmax 1010

char s[nmax];
int n, m, a[nmax][nmax], b[30], c[nmax][nmax][30], sol, v[30];

int main()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%d %d\n",&m,&n);
	int i, j, k, ok;
	for (i=1; i<=m; i++)
	{
		fgets(s, nmax, stdin);
		for (j=1; j<=m; j++) a[i][j]=s[j-1]-'a'+1;
	}
	for (i=0; i<n; i++) 
	{
		fgets(s, nmax, stdin);
		for (j=0; j<n; j++) v[s[j]-'a'+1]++;
	}
	for (i=1; i<=m; i++)
		for (j=1; j<=m; j++)
		{
			for (k=1; k<=26; k++)
				c[i][j][k]=c[i-1][j][k];
			c[i][j][a[i][j]]++;
		}
	for (i=n; i<=m; i++)
	{
		for (k=1; k<=26; k++) b[k]=0;
		for (j=1; j<=m; j++)
		{
			for (k=1; k<=26; k++) b[k]=b[k]+c[i][j][k]-c[i-n][j][k];
			if (j>n)
				for (k=1; k<=26; k++) b[k]=b[k]-c[i][j-n][k]+c[i-n][j-n][k];
			ok=1;
			for (k=1; k<=26; k++)
				if (b[k]!=v[k]) 
				{
					ok=0;
					break;
				}
			sol+=ok;
		}
	}
	printf("%d\n",sol);
}