Cod sursa(job #498281)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 4 noiembrie 2010 19:21:17
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#define nmax 1010

char s[nmax];
int n, m, a[nmax][nmax], b[30], r[nmax][30], d[nmax][30], c[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++) c[j][a[i][j]]++;
		if (i>=n) 
		{
			for (j=1; j<=m; j++) d[j][a[i-n][j]]++;
			for (j=1; j<=m; j++)
				for (k=1; k<=26; k++) r[j][k]=c[j][k]-d[j][k];
			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]+r[j][k];
				if (j>=n)
				{
					for (k=1; k<=26; k++) b[k]-=r[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);
}