Cod sursa(job #494928)

Utilizator ooctavTuchila Octavian ooctav Data 23 octombrie 2010 13:10:19
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<cstdio>
#include<iostream>
using namespace std;

const int NMAX = 1005;
const int MMAX = 1005;
const char CH = 'a';
const int ALFA = 26;

int N, M, REZ;
char A[NMAX][NMAX];
char B[MMAX][MMAX];

int cA[NMAX][NMAX], cB[ALFA];
int merg[NMAX][NMAX];

void citire()
{
	scanf("%d%d\n", &N, &M);
	for(int i = 1 ; i <= N ; i++)
		gets(A[i]+1);
		
	for(int i = 1 ; i <= M ; i++)
		gets(B[i]+1);
}

void obt_cB()
{
	for(int i = 1 ; i <= M ; i++)
		for(int j = 1 ; j <= M ; j++)
			cB[B[i][j] - CH]++;
}

void dinamic(char k)
{
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= N ; j++)
		{
			cA[i][j] = cA[i - 1][j] + cA[i][j - 1] - cA[i - 1][j - 1];
			if(k == A[i][j] - CH)
				cA[i][j]++;
		}
}

void verifica(char k)
{
	for(int i = M ; i <= N ; i++)
		for(int j = M ; j <= N ; j++)
			if(cA[i][j] - cA[i - M][j] - cA[i][j - M] + cA[i - M][j - M] != cB[k])
				merg[i][j] = 1;
}

void numara()
{
	for(int i = M ; i <= N ; i++)
		for(int j = M ; j <= N ; j++)
			REZ += 1 - merg[i][j];
}

void scrie()
{
	printf("%d\n", REZ);
}

int main()
{
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	citire();
	obt_cB();
	for(char k = 0 ; k < ALFA ; k++)
	{
		dinamic(k);
		verifica(k);
	}
	numara();
	scrie();
	return 0;
}