Cod sursa(job #493273)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 17 octombrie 2010 17:54:54
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
/*  
v[i][j][k] -> de cate ori apare litera k in genom pe coloana j incepand cu linia i n campuri in jos (n-1)

v[i][j] -> o config

iau coloanele
pt fiecare
calc
apoi prin adaugare si scoatere de la capete.
apoi iau fiecare elem si adun elem in ordine (primele n), compar cu virusul, apoi avansez (scot din stanga, pun in dreapta), pana ajung la capat; apoi urmat linie (la fiecare linie recalculez).


*/ 

#include <cstdio>
#include <cstring>

const int M = 1001; const int N = 1001;
const int L = 27;
const int S = M;
 
short v[M][M][L];
char g[M][M]; int m,n;
short config_virus[L];
char s[S];

short cod(char l)
{
	return l - 'a';
}

void citire()
{
	char litera_virus;
	scanf("%i%i\n",&m,&n);
	for (int i = 1; i <= m; ++i)
	{
		gets(s);
		for (int j = 1; j <= m; ++j)
			g[i][j] = s[j-1];
	}
	for (int i = 1; i <= n; ++i)
	{
		gets(s);
		for (int j = 1; j <= n; ++j)
			++config_virus[cod(s[j-1])];
	}
}

void resetare_config(short config[])
{
	for (int i = 0; i <= 25; ++i)
		config[i] = 0;
}

inline void adaugare_litera_config(short config[],char l)
{
	++config[cod(l)];
}

inline void scoatere_litera_config(short config[],char l)
{
	--config[cod(l)];
}

void adaugare_config(short config[],short config_adaugat[])
{
	for (int i = 0; i <= 26; ++i)
		config[i] += config_adaugat[i];
}

void scoatere_config(short config[],short config_scos[])
{
	for (int i = 0; i <= 26; ++i)
		config[i] -= config_scos[i];
}

bool config_egale(short config1[], short config2[])
{
	for (int i = 0; i <= 26; ++i)
		if (config1[i] != config1[i])
			return false;
	return true;
}


void calculare_v()
{
	short config[26];
	for (int j = 1; j <= m; ++j)
	{
		resetare_config(config);
		for (int i = 1; i <= n; ++i)
			adaugare_litera_config(config,g[i][j]);
		memcpy(v[1][j],config,L*sizeof(v[0][0][0]));
		for (int i = 2; i <= m-n+1; ++i)
		{
			scoatere_litera_config(config,g[i-1][j]);
			adaugare_litera_config(config,g[i+n-1][j]);
			memcpy(v[i][j],config,L*sizeof(v[0][0][0]));
		}
	}
}

void folosire_v()
{
	int nr_ap_virus=0;
	short config[26];
	for (int i = 1; i <= m-n+1; ++i)
	{
		resetare_config(config);
		for (int j = 1; j <= n; ++j)
			adaugare_config(config,v[i][j]);
		if (config_egale(config,config_virus))
			++nr_ap_virus;
		for (int j = 2; j <= m-n+1; ++j)
		{
			scoatere_config(config,v[i][j-1]);
			adaugare_config(config,v[i][j+n-1]);
			if (config_egale(config,config_virus))
				++nr_ap_virus;
		}
	}
	printf("%i",nr_ap_virus);
}

int main()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	citire();
	calculare_v();
	folosire_v();
	return 0;
}