Cod sursa(job #556778)

Utilizator mihai995mihai995 mihai995 Data 16 martie 2011 12:16:09
Problema Matrix Scor 70
Compilator cpp Status done
Runda matrice_ Marime 1.12 kb
#include <fstream>
using namespace std;

const int N=1001;
int a[N][N][27],v[27],aux[27],n,m;
char s[N];

ifstream in("matrix.in");
ofstream out("matrix.out");

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

void sub(int a[],int b[])
{
	for (int i=0;i<27;i++)
		a[i]-=b[i];
}

void read(int v[N][N][27],int n)
{
	for (int i=1;i<=n;i++)
	{
		in.getline(s+1,n+1);
		for (int j=1;s[j];j++)
		{
			v[i][j][s[j]-'a']++;
			add(v[i][j],v[i-1][j]);
			add(v[i][j],v[i][j-1]);
			sub(v[i][j],v[i-1][j-1]);
		}
	}
}

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

void define(int v[N],int x,int y,int z,int t)
{
	for (int i=0;i<27;i++)
		v[i]=0;
	add(v,a[z][t]);
	add(v,a[x][y]);
	sub(v,a[x][t]);
	sub(v,a[z][y]);
}

int main()
{
	int i,j,nr=0;
	in>>n>>m>>ws;
	read(a,n);
	for (i=1;i<=n;i++)
	{
		in.getline(s+1,n+1);
		for (j=1;s[j];j++)
			v[s[j]-'a']++;
	}
	for (i=1;i<=n-m+1;i++)
		for (j=1;j<=n-m+1;j++)
		{
			define(aux,i-1,j-1,i+m-1,j+m-1);
			nr+=egal(aux,v);
		}
	out<<nr<<"\n";
	return 0;
}