Pagini recente » Profil Alex_tz307 | Clasament pregatireoli10_1 | Prime | Prieteni | Cod sursa (job #492056)
Cod sursa(job #492056)
#include<cstdio>
const int N=1005;
const int M=30;
int a[N][N],m,n,fra[M],frb[M],sum[N][N][M];
void citmat(int &m,int a[N][N])
{
char s[N];
for (int i=1;i<=m;++i)
{
gets(s);
for (int j=0;j<m;++j)
a[i][j+1]=s[j]-'a';
}
}
void citire()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d",&m,&n);
citmat(m,a);
}
void calculc()
{
char x[N];
for (int i=1;i<=n;++i)
{
gets(x+1);
for (int j=1;j<=n;++j)
{
if(i<n && j<n)
fra[a[i][j]]++;
frb[x[j]-'a']++;
}
}
}
void actualfra(int i1,int i2)
{
for (int j=1;j<n;++j)
{
fra[a[i2][j]]++;
fra[a[i1-1][j]]--;
}
}
void cop(int a,int b)
{
for (int k=0;k<26;++k)
sum[a][b][k]=sum[a][b-1][k];
}
void calculsum()
{
for (int j=1;j<=m;++j)
sum[1][j][a[1][j]]++;
for (int i=2;i<=m;++i)
for (int j=1;j<=m;++j)
{
cop(i,j);
sum[i][j][a[i][j]]++;
}
}
bool verif()
{
for (int i=0;i<26;++i)
if (fra[i]!=frb[i])
return false;
return true;
}
void actual()
{
int i1,i2,c1,c2;
for (i1=1,i2=n;i2<m;++i1,++i2)
for (c1=1,c2=n;c2<m;++c1,++c2)
for (int k=0;k<26;++k)
fra[k]+=sum[i2][c2+1][k]-sum[i1-1][c2+1][k]-(sum[i2][c1][k]-sum[i1-1][c1][k]);
}
int main()
{
citire();
calculc();
int i1,i2,j1,j2,nr=0;
for (i1=1,i2=n;i2<m;++i1,++i2)
{
actualfra(i1,i2);
for (j1=1,j2=n;j2<=m;++j1,++j2)
{
actual();
if (verif())
++nr;
}
}
printf("%d\n",nr);
return 0;
}