Cod sursa(job #914882)

Utilizator marius135Dumitran Adrian Marius marius135 Data 14 martie 2013 15:45:04
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<fstream>

using namespace std;

#define maxn 1024

char a[maxn][maxn], b[maxn];
int nr_rez[26], nr[maxn][26];

bool ver( int *a, int *b) {
	
	bool ok = 1;
	for( int i = 0; i < 26; ++i) {
		//cout<<'a' + i<<" "<<a[i]<<" "<<b[i]<<endl;
		if( a[i] != b[i])
			ok = 0;
	}
	
	return ok;
}

int main() {
	
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	int N, M;
	scanf("%d %d", &N, &M);
	for( int i = 0; i < N; ++i) {
		scanf("%s", a[i]);
	}
	for( int j = 1; j <= M; ++j) {
		scanf("%s", b);
		for(int j = 0; j < M; ++j)
			nr_rez[b[j] -'a']++;
	}
	for( int i = 0; i < M; ++i) {
		for( int j = 0; j < N; ++j){
			nr[j][a[i][j]-'a']++;
		}
	}
	int total = 0;
	for( int i = M  ; i <= N; ++i) {
		int sol[26];
		memset(sol, 0, sizeof(sol));
		for( int j = 0; j < M; ++j) {
			for( int k = 0; k < 26; ++k)
				sol[k] += nr[j][k];
		}	
		total += ver(sol, nr_rez);
		for( int j = M; j < N; ++j) {
			for( int k = 0; k < 26; ++k)
				sol[k] = sol[k] - nr[j- M][k] + nr[j][k];
			total += ver(sol, nr_rez);
		}
		for( int j = 0; j < N; ++j) {
			nr[j][ a[i-M][j]-'a']--;
			nr[j][ a[i][j]-'a']++;
		}
	}
	
	cout<<total;
	
	return 0;
	
}