Cod sursa(job #343778)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 27 august 2009 12:26:48
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
char s[1100][1100],ok[1100][1100],scit[1100],*cit,c;
int n,m,i,j,d[1100][1100],cnt[30],Cnt,sol;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		cit=&s[i][1];
		scanf("%s",cit);
	}
	cit=scit;
	for(i=1;i<=m;i++)
	{
		scanf("%s",cit);
		for(j=0;j<m;j++)cnt[cit[j]-'a']++;
	}
}
void solve()
{
	for(i=m;i<=n;i++)
		for(j=m;j<=n;j++)
			ok[i][j]=1;
	for(c='a';c<='z';c++)
	{
		if(!cnt[c-'a'])continue;
		Cnt=cnt[c-'a'];
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+(s[i][j]==c);
		for(i=m;i<=n;i++)
			for(j=m;j<=n;j++)
				if(ok[i][j])
					ok[i][j]=d[i][j]-d[i-m][j]-d[i][j-m]+d[i-m][j-m]==Cnt;
	}
	for(i=m;i<=n;i++)
		for(j=m;j<=n;j++)
			sol+=ok[i][j];
	printf("%d\n",sol);
}