Cod sursa(job #520769)

Utilizator mihai995mihai995 mihai995 Data 10 ianuarie 2011 12:18:16
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
using namespace std;

char a[1<<10][1<<10],b[1<<10];
bool r[1<<10][1<<10];
int v[1<<10][1<<10],nr[1<<5],n,m;

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

int main()
{
	int i,j,q=0;
	char x;
	in>>m>>n>>ws;
	if (m<n)
	{
		out<<"0\n";
		return 0;
	}
	for (i=1;i<=m;i++)
		in.getline(a[i]+1,m+1);
	for (i=1;i<=n;i++)
	{
		in.getline(b+1,n+1);
		for (j=1;b[j];j++)
			nr[b[j]-'a']++;
	}
	for (i=1;i<=m-n+1;i++)
		for (j=1;j<=m-n+1;j++)
			r[i][j]=true;
	for (x='a';x<='z';x++)
	{
		for (i=1;i<=m;i++)
			for (j=1;j<=m;j++)
				v[i][j]=(a[i][j]==x)+v[i-1][j]+v[i][j-1]-v[i-1][j-1];
		for (i=0;i<=m-n;i++)
			for (j=0;j<=m-n;j++)
				if (v[i+n][j+n]-v[i+1][j+n]-v[i+n][j+1]+v[i+1][j+1]!=nr[x-'a'])
					r[i+1][j+1]=false;
	}
	for (i=1;i<m-n;i++)
		for (j=1;j<m-n;j++)
			q+=r[i][j];
	out<<q<<"\n";
	return 0;
}