Cod sursa(job #494915)

Utilizator ooctavTuchila Octavian ooctav Data 23 octombrie 2010 12:53:42
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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][ALFA], cB[MMAX][MMAX][ALFA];

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 dinamic()
{
	for(int i = 1 ; i <= N ; i++)
		for(int j = 1 ; j <= N ; j++)
		{
			for(int k = 0 ; k < 26 ; k++)
				cA[i][j][k] = cA[i - 1][j][k] + cA[i][j - 1][k] - cA[i - 1][j - 1][k];
			cA[i][j][A[i][j] - CH]++;
		}
			
	for(int i = 1 ; i <= M ; i++)
		for(int j = 1 ; j <= M ; j++)
		{
			for(int k = 0 ; k < 26 ; k++)
				cB[i][j][k] = cB[i - 1][j][k] + cB[i][j - 1][k] - cB[i - 1][j - 1][k];
			cB[i][j][B[i][j] - CH]++;
		}
}

void numara()
{
	for(int i = M ; i <= N ; i++)
		for(int j = M ; j <= N ; j++)
		{
			int b = 1;
			for(int k = 0 ; k < 26 ; k++)
				if(cA[i][j][k] - cA[i - M][j][k] - cA[i][j - M][k] + cA[i - M][j - M][k] != cB[M][M][k])
				{
					b = 0;
					break;
				}
			REZ += b;
		}
}

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

int main()
{
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	citire();
	dinamic();
	numara();
	scrie();
	return 0;
}