Cod sursa(job #3674)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 27 decembrie 2006 16:28:24
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
#define fin "matrix.in"
#define fout "matrix.out"
#define NMAX 1001
char map[NMAX][NMAX],vir[NMAX][NMAX];
int forw[NMAX][27],back[NMAX][27],back1[NMAX][27],forw1[NMAX][27],tmp[27];
int sol,n,m,v[NMAX][NMAX][27],v2[27];
FILE *in,*out;

int main() {
int i,j,k;
	in=fopen(fin,"r"); out=fopen(fout,"w");
	fscanf(in,"%i%i",&n,&m);
	for (i=1;i<=n;++i) {
		fgetc(in);
		for (j=1;j<=n;++j) { 
			map[i][j]=fgetc(in);
			map[i][j]-='a';
		}
	}
	for (i=1;i<=m;++i) {
		fgetc(in);
		for (j=1;j<=m;++j) { 
			vir[i][j]=fgetc(in);
			vir[i][j]-='a';
			v2[(int)vir[i][j]]++;
		}
	}
	for (i=1;i<=n;++i) {
	
		for (j=1;j<=n;++j) {
		
			for (k=0;k<=26;++k) { 
				forw[j][k]=forw[j-1][k]+forw1[j][k]-forw1[j-1][k];
				tmp[k]=0;
			}
		
			forw[j][(int)map[i][j]]++;
			
			if (i-m>0) {

				for (k=0;k<=26;++k) 

					back[j][k]=back[j-1][k]+back1[j][k]-back1[j-1][k];
				
				back[j][(int)map[i-m][j]]++;
			}

			if (i>=m && j>=m) { 
			
				for (k=0;k<=26;++k) 
				
					tmp[k]=forw[j][k]-back[j][k]-forw[j-m][k]+back[j-m][k];
			
				for (k=0;k<=26 && tmp[k]==v2[k];++k);
		       		
				if (k>26) sol++;	
			}

		}

		for (j=1;j<=n;++j) 
		for (k=0;k<=26;++k) {

			forw1[j][k]=forw[j][k];
			back1[j][k]=back[j][k];
		}

	}
	
	fprintf(out,"%i\n",sol);

	fclose(in); fclose(out);
	
	return 0;	
	
}