Cod sursa(job #556090)

Utilizator lianaliana tucar liana Data 15 martie 2011 22:16:36
Problema Matrix Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#define nmax 1003
long int rez, i, la, lb, j, lin, col, nr['z'+2], nrb['z'+2], nr1['z'+2];
char a[nmax][nmax], b[nmax][nmax], c, cc;
bool ok;

void comparare()
{
	ok=true;
	for (cc='a';cc<='z';cc++)
		if (nr[cc]!=nrb[cc])
		{	ok=false;	break;	}
	rez+=ok;
}

int main()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%ld %ld\n",&la, &lb);
	for (i=1;i<=la;i++)
		gets(a[i]);
	for (i=1;i<=lb;i++)
		gets(b[i]);
	for (i=1;i<=lb;i++)
		for (j=0;j<lb;j++)
		{	nr[a[i][j]]++;	nrb[b[i][j]]++;		}
		
	for (lin=1;lin<=la-lb+1;lin++)
	{
		if (lin>1)
		{
			for (c='a';c<='z';c++)
				nr[c]=nr1[c];
			for (j=0;j<lb;j++)
			{	nr[a[lin-1][j]]--;	nr[a[lin+lb-1][j]]++;	}
		}
		
		for (c='a';c<='z';c++)
			nr1[c]=nr[c];
		comparare();
		for (col=1;col<=la-lb;col++)
		{
			for (i=lin;i<=lin+lb-1;i++)
			{	nr[a[i][col-1]]--; nr[a[i][col+lb-1]]++;}
			comparare();
		}
	}
	printf("%ld",rez);
	return 0;
}