Cod sursa(job #44827)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 31 martie 2007 19:07:48
Problema Matrix Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
# include <stdio.h>
# include <string.h>

# define  _fin	"matrix.in"
# define  _fout "matrix.out"

# define  maxn	1001
# define  sigma 'z'


int n, m, i, j, f[sigma], aux, sol,
	o[maxn][maxn], t[maxn][maxn];
char a[maxn][maxn], b[maxn][maxn], c;


void readf()
{
	freopen(_fin, "r", stdin);
	for (scanf("%d%d", &n, &m), i=1; i<=n; i++) scanf("%s", a[i]+1);
	for (i=1; i<=m; i++) {
		scanf("%s", b[i]+1);
		for (j=1; j<=m; j++) ++f[b[i][j]];
	}
}

void solve()
{
	for (i=1; i<=n; i++) for (j=1; j<=n; j++) o[i][j]=1;
	
	for (c='a'; c<='z'; c++) {
		memset(t, 0, sizeof(t));
		for (i=1; i<=n; i++)
			for (j=1; j<=n; j++)
				t[i][j] = t[i-1][j]+t[i][j-1]-t[i-1][j-1]+(a[i][j]==c);
		
		for (i=m; i<=n; i++)
			for (j=m; j<=n; j++) {
				aux = t[i][j]-t[i-m][j]-t[i][j-m]+t[i-m][j-m];
				o[i][j] &= (aux==f[c]);
			}
	}
	
	for (i=m; i<=n; i++)
		for (j=m; j<=n; j++) sol += o[i][j];
}

int main()
{
	readf();
	solve();
	
	fprintf(fopen(_fout,"w"), "%d\n", sol);
	
	return 0;
}