Cod sursa(job #774277)

Utilizator maritimCristian Lambru maritim Data 4 august 2012 00:31:57
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>

FILE *f = fopen("matrix.in","r");
FILE *g = fopen("matrix.out","w");

#define MaxM 1002
#define sh short int
#define MaxSig 26

int N,M,Sol;
char A[MaxM][MaxM],S[MaxM];
sh C[MaxM][MaxM][MaxSig];
int Best[MaxSig],BestM[MaxSig],Comp[MaxSig];

void citire(void)
{
	fscanf(f,"%d %d\n",&M,&N);
	for(int i=1;i<=M;i++)
		fgets(A[i],sizeof(A[i]),f);
	for(int i=1;i<=N;i++)
	{
		fgets(S,sizeof(S),f);
		for(int j=0;j<N;j++)
			++ Comp[S[j]-'a'];
	}
}

void Preprocesare(void)
{	
	for(int i=0;i<M;i++)
	{
		for(int j=1;j<=N;j++)
			++ C[1][i][A[j][i]-'a'];
			
		for(int j=2;j<=M-N+1;j++)
		{
			-- C[j][i][A[j-1][i]-'a'];
			++ C[j][i][A[j+N-1][i]-'a'];
			
			for(int k=0;k<=25;k++)
				C[j][i][k] += C[j-1][i][k];
		}
		
	}
}

inline int Verif(void)
{
	for(int i=0;i<25;i++)
		if(Best[i] != Comp[i])
			return 0;
			
	return 1;
}

void Rezolvare(void)
{
	Preprocesare();
	
	for(int i=1;i<=N;i++)
		for(int j=0;j<N;j++)
			++ BestM[A[i][j]-'a'],++ Best[A[i][j]-'a'];
	
	for(int i=1;i<=M-N+1;i++)
	{
		for(int j=0;j<=M-N;j++)
		{
			Sol += Verif();
			
			if(j<M-N)
			for(int k=0;k<=25;k++)
				Best[k] += (-C[i][j][k]+C[i][j+N][k]);
		}
		
		for(int k=0;k<N;k++)
			-- BestM[A[i][k]-'a'], ++BestM[A[i+N][k]-'a'];
			
		for(int k=0;k<25;k++)
			Best[k] = BestM[k];
	}
}

int main()
{
	citire();
	Rezolvare();
	
	fprintf(g,"%d\n",Sol);
}