Cod sursa(job #3136120)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 5 iunie 2023 14:39:33
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
//Ilie Dumitru
#include<cstdio>
#include<bitset>
const int NMAX=1024;

int N, M;
char mat[NMAX][NMAX], subMat[NMAX];
int cnt[NMAX][NMAX], sub[26];
std::bitset<NMAX> ok[NMAX];

int main()
{
	FILE* f=fopen("matrix.in", "r"), *g=fopen("matrix.out", "w");
	int i, j, k, ans=0;

	fscanf(f, "%d%d", &M, &N);
	fgets(mat[0], NMAX, f);
	for(i=0;i<M;++i)
		fgets(mat[i], NMAX, f);

	for(i=0;i<N;++i)
	{
		fgets(subMat, NMAX, f);
		for(j=0;j<N;++j)
			++sub[subMat[j]-'a'];
	}

	for(i=N;i<=M;++i)
		for(j=N;j<=M;++j)
			ok[i][j]=1;

	for(k=0;k<26;++k)
	{
		for(i=1;i<=M;++i)
			for(j=1;j<=M;++j)
			{
				cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+(mat[i-1][j-1]=='a'+k);
				if(i>=N && j>=N && cnt[i][j]-cnt[i][j-N]-cnt[i-N][j]+cnt[i-N][j-N]!=sub[k])
					ok[i][j]=0;
			}
	}

	for(i=N;i<=M;++i)
		for(j=N;j<=M;++j)
			ans+=ok[i][j];

	fprintf(g, "%d\n", ans);

	fclose(f);
	fclose(g);
	return 0;
}