Cod sursa(job #477115)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 13 august 2010 15:17:45
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#include <string.h>

int n, m, f[30];
char s[1030][1030];
int v[1030][1030], ok[1030][1030];

int main ()
{
	freopen ("matrix.in", "r", stdin);
	freopen ("matrix.out", "w", stdout);
	
	scanf ("%d %d", &n, &m);
	
	int i, j, k;
	
	for (i = 1; i <= n; i ++)
		gets (s[i] + 1);
	
	for (i = 1; i <= m; i ++)
	{
		gets (s[0] + 1);
		for (j = 1; j <= m; j ++)
			f[s[0][j] - 'a'] ++;
	}
	
	for (i = m; i <= n; i ++)
		for (j = m; j <= n; j ++)
			ok[i][j] = 1;
	
	for (k = 0; k < 26; k ++)
	{
		memset (v, 0, sizeof (v));
		
		for (i = 1; i <= n; i ++)
			for (j = 1; j <= m; j ++)
			{
				v[i][j] = v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1] + (s[i][j] == k);
				
				if (ok[i][j] && i >= m && j >= m)
					ok[i][j] = (v[i][j] - v[i - m][j] - v[i][j - m] + v[i - m][j - m]) == f[k]; 
			}
	}
	
	int sol = 0;
	for (i = m; i <= n; i ++)
		for (j = m; j <= n; j ++)
			sol += ok[i][j];
	printf ("%d\n", sol);
	return 0;
}