Cod sursa(job #635879)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 19 noiembrie 2011 15:23:25
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#define val 1009
int n , m , i , j , k , h , c,sol;
char V[val][val] , a[val];
int Z[val][val];
int Ok[val][val];
int Fr[300];
int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%d%d\n",&m,&n);
	sol=(m-n+1)*(m-n+1);
	for(i=1;i<=m;i++){		
		scanf("%s",V[i]+1);		
	}	
	scanf("\n");
	for(i=1;i<=n;i++){		
		scanf("%s",a+1);
		for(j=1;j<=n;j++)
			Fr[a[j]]++;		
	}
	for(i='a';i<='z';i++){
		if(Fr[i]==0)
			continue;
		for(j=1;j<=m;j++){
			for(k=1;k<=m;k++){
				Z[j][k]=Z[j-1][k]+Z[j][k-1]-Z[j-1][k-1];
				if(V[j][k]==i)
					Z[j][k]++;
				if(j>=n&&k>=n&&Ok[j][k]==0){
					h=Z[j][k]-Z[j][k-n]-Z[j-n][k]+Z[j-n][k-n];
					if(h!=Fr[i]){
						if(Ok[j][k]==0)
							sol--;
						Ok[j][k]=1;						
					}
				}
			}			
		}
	}
	/*for(i=n;i<=m;i++){
		for(j=n;j<=m;j++){
			if(Ok[i][j]==0)
				c++;
		}
	}*/
	printf("%d",c);
	return 0;
}