Cod sursa(job #731992)

Utilizator danalex97Dan H Alexandru danalex97 Data 9 aprilie 2012 15:18:45
Problema Matrix Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
using namespace std;

ifstream F("matrix.in");
ofstream G("matrix.out");

#define Sigma 30
#define Lim 1011
typedef int List[Sigma];

#define nat(a) ( int(a)-int('a')+1 )

int N,M,Co;
List A[Lim][Lim];
List B;

char Mat[Lim][Lim];
char Mat2[Lim][Lim];

inline void Add(List& A,List B)
{	for (int ii=1;ii<=Sigma;++ii)
		A[ii]+=B[ii]; }

inline void Dec(List& A,List B)
{	for (int ii=1;ii<=Sigma;++ii)
		A[ii]-=B[ii]; }

inline int cmp(List A,List B)
{	for (int ii=1;ii<=Sigma;++ii)
		if ( A[ii]!=B[ii] )
			return 0;
	return 1; }

int main(void)
{
	F>>N>>M;
	F.getline(Mat[1],N+1,'\n');
	for (int i=1;i<=N;++i)
	{
		F.getline(Mat[i],N+1,'\n');
		for (int j=N;j;--j) Mat[i][j]=Mat[i][j-1];
	}
	for (int i=1;i<=M;++i)
	{
		F.getline(Mat2[i],M+1,'\n');
		for (int j=M;j;--j) Mat2[i][j]=Mat2[i][j-1];
	}
	
	for (int i=1;i<=M;++i)
		for (int j=1;j<=M;++j)
			++B[nat(Mat2[i][j])];
	
	for (int i=1;i<=N;++i)
		for (int j=1;j<=N;++j)
		{
			Add(A[i][j],A[i-1][j]);
			Add(A[i][j],A[i][j-1]);
			Dec(A[i][j],A[i-1][j-1]);
			++A[i][j][nat(Mat[i][j])];
		}
	
	for (int i=M;i<=N;++i)
		for (int j=M;j<=N;++j)
		{
			Add(A[i][j],A[i-M][j-M]);
			Dec(A[i][j],A[i-M][j]);
			Dec(A[i][j],A[i][j-M]);
		}
	
	for (int i=M;i<=N;++i)
		for (int j=M;j<=N;++j)
			if ( cmp( A[i][j],B ) )
				++Co;
	
	G<<Co<<'\n';
	
	F.close();
	G.close();
}