Cod sursa(job #554337)

Utilizator HoriaClementHoriaC HoriaClement Data 14 martie 2011 19:24:14
Problema Matrix Scor 100
Compilator cpp Status done
Runda matrice_ Marime 0.88 kb
#include <fstream>

using namespace std;

int n,m,f[28];

const int N=1005;
char s[N][N];
int v[N][N],verific[N][N],rez;

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

void citire()
{
	in>>n>>m>>ws;
	for (int i=1;i<=n;++i)//mat1
		in.getline(s[i]+1,n+1);
	for (int i=1;i<=m;++i)//mat2
	{
		in.getline(s[0]+1,m+1);
		for(int j=1;j<=m;++j)//frecv 
			++f[s[0][j]-'a'];
	}
}
void work()
{
	for(int i=m;i<=n;++i)
		for(int j=m;j<=n;++j)//vect aux o(m2)
			verific[i][j]=1;
	for(int k=0; k<26;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
			{
				v[i][j]=v[i-1][j]+v[i][j-1]-v[i-1][j-1]+(s[i][j]==k+'a');//rel de rec
				if (verific[i][j] && i>=m && j>=m)
					verific[i][j]=(v[i][j]-v[i-m][j]-v[i][j-m]+v[i-m][j-m])==f[k]; 
			}
	for(int i=m;i<=n;++i)
		for(int j=m;j<=n;++j)
			rez+=verific[i][j];//adun la rez
	out<<rez;
}
int main ()
{
	citire();
	work();
	return 0;
}