Cod sursa(job #556771)

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

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

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

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

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

void read(short int v[N][N][27],short int n)
{
	for (short int i=1;i<=n;i++)
	{
		in.getline(s+1,n+1);
		for (short 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(short int a[],short int b[])
{
	for (short int i=0;i<27;i++)
		if (a[i]!=b[i])
			return false;
	return true;
}

void define(short int v[N],short int x,short int y,short int z,short int t)
{
	for (short 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()
{
	short 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;
}