Cod sursa(job #999147)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 19 septembrie 2013 13:54:37
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
using namespace std;
int n,m,fr[30],nr[1010][1010],sol;
char mat[1010][1010],s[1010];
bool wrong[1010][1010];

int main()
{
	int i,j,c,frnow;
	ifstream fin("matrix.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
		fin>>(mat[i]+1);
	for(i=1;i<=m;i++)
	{
		fin>>(s+1);
		for(j=1;j<=m;j++)
			fr[s[j]-'a']++;
	}
	fin.close();
	
	for(c=0;c<26;c++)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				nr[i][j]=nr[i-1][j]+nr[i][j-1]-nr[i-1][j-1];
				if(mat[i][j]-'a'==c)
					nr[i][j]++;
				if(i>=m && j>=m && !wrong[i][j])
				{
					frnow=nr[i][j]-nr[i-m][j]-nr[i][j-m]+nr[i-m][j-m];
					if(frnow!=fr[c])
						wrong[i][j]=true;
				}
			}
		}
	}
	for(i=m;i<=n;i++)
		for(j=m;j<=n;j++)
			if(!wrong[i][j])
				sol++;
	
	ofstream fout("matrix.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}