Cod sursa(job #178485)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 14 aprilie 2008 17:50:41
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream.h>

void constr (int v[30], char a[1001][1001], int m)
	{
	int i,j;
	for (i=1;i<=m;i++)
		for (j=1;j<=m;j++)
			v[a[i][j]-'a'+1]++;
	}

void updtl (int v[30], char a[1001][1001],int m, int p, int u)
	{
	int i;
	for (i=1;i<=m;i++)
		v[a[p][i]-'a'+1]--;
	for (i=1;i<=m;i++)
		v[a[u][i]-'a'+1]++;
	}

void updtc (int v[30], char a[1001][1001], int m, int p, int u, int l)
	{
	int i;
	for (i=1;i<=m;i++)
		v[a[l+i-1][p]-'a'+1]--;
	for (i=1;i<=m;i++)
		v[a[l+i-1][u]-'a'+1]++;
	}

int main()
{
int i,j,n,m,nr=0,v[30],v1[30],t[30];
char ch,a[1001][1001];
ifstream f("matrix.in");
f>>n>>m;
for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
		f>>a[i][j];
memset(v,0,sizeof(v));
for (i=1;i<=m;i++)
	for (j=1;j<=m;j++)
		{
		f>>ch;
		v[ch-'a'+1]++;
		}
f.close();
memset(v1,0,sizeof(v1));memset(t,0,sizeof(t));
for (i=1;i<=n-m+1;i++)
	{
	if (i==1) { constr(v1,a,m);memcpy(t,v1,sizeof(v1));}
		else {
		     updtl(t,a,m,i-1,m+i-1);
		     memcpy(v1,t,sizeof(t));
		     }
	if (memcmp(v1,v,sizeof(v))==0) nr++;
	for (j=2;j<=n-m+1;j++)
		{
		updtc(v1,a,m,j-1,j+m-1,i);
		if (memcmp(v1,v,27)==0) nr++;
		}
	}
ofstream g("matrix.out");
g<<nr;g.close();
return 0;
}