Cod sursa(job #270243)

Utilizator CezarMocanCezar Mocan CezarMocan Data 3 martie 2009 20:37:35
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <cstring>

using namespace std;

int n, m, i, j, v[1010][1010], x[1010][1010], col[1010][30];
char s[1010];
int curr[30], nd[30], sol;

inline bool egal(int a[], int b[]) {
	for (int i = 1; i <= 27; i++)
		if (a[i] != b[i])
			return false;
	return true;
}

inline void scad(int a[], int b[]) {
	for (int i = 1; i <= 27; i++)
		a[i] -= b[i];
}

inline void add(int a[], int b[]) {
	for (int i = 1; i <= 27; i++)
		a[i] += b[i];
}


int main() {
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	
	scanf("%d %d ", &n, &m);
	
	for (i = 1; i <= n; i++) {
		fgets(s, 1010, stdin);
		for (j = 0; j < n; j++)
			v[i][j + 1] = s[j] - 'a' + 1;
	}
	
	for (i = 1; i <= m; i++) {
		fgets(s, 1010, stdin);
		for (j = 0; j < m; j++) 
			x[i][j + 1] = s[j] - 'a' + 1;
	}
	
	for (i = 1; i <= m; i++)
		for (j = 1; j <= n; j++)
			col[j][v[i][j]]++;
		
	for (i = 1; i <= m; i++)
		for (j = 1; j <= m; j++) {
			nd[x[i][j]]++;
			curr[v[i][j]]++;
		}
		
	for (i = m; i <= n; i++) {
		//mai intai fac jmenu pe coloane apoi recalculez col[i]
		for (j = m; j <= n; j++) {
			if (egal(curr, nd))
				sol++;
			scad(curr, col[j - m + 1]);
			add(curr, col[j + 1]);
		}
		for (j = 1; j <= n; j++) {
			col[j][v[i - m + 1][j]]--;
			col[j][v[i + 1][j]]++;
		}
		memset(curr, 0, sizeof(curr));
		for (j = 1; j <= m; j++)
			add(curr, col[j]);
	}
	
	printf("%d\n", sol);
	
	return 0;
}