Cod sursa(job #249305)

Utilizator ProtomanAndrei Purice Protoman Data 27 ianuarie 2009 23:36:40
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <algorithm>
#define MAX 1024
using namespace std;

int n, m, rez;
int matAp[MAX][MAX], valid[MAX][MAX], matLin[MAX][MAX];
int apLitera[26];
char matInit[MAX][MAX];

int main()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	
	scanf("%d %d\n", &m, &n);

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%c", &matInit[i][j]);

			valid[i][j] = 1;
		}

		scanf("\n");
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			char elMatrix;
			scanf("%c", &elMatrix);

			apLitera[elMatrix - 'a']++;
		}

		scanf("\n");
	}

	for (int lit = 0; lit < 26; lit++)
		for (int i = 1; i <= m; i++)
		{
			memset(matLin[i], 0, sizeof(matLin[i]));

			for (int j = 1; j <= m; j++)
			{
				matLin[i][j] = matLin[i][j - 1];
				if (matInit[i][j] - 'a' == lit)
					matLin[i][j]++;
				if (j > n && matInit[i][j - n] - 'a' == lit)
					matLin[i][j]--;

				matAp[i][j] = matAp[i - 1][j] + matLin[i][j];
				if (i > n)
					matAp[i][j] -= matLin[i - n][j];

				if (matAp[i][j] != apLitera[lit])
					valid[i][j] = 0;
			}
		}

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= m; j++)
			rez += valid[i][j];

	printf("%d\n", rez);

	fclose(stdin);
	fclose(stdout);
	return 0;
}