Pagini recente » Cod sursa (job #925731) | Cod sursa (job #2282213) | Cod sursa (job #2565182) | Cod sursa (job #2860939) | Cod sursa (job #492609)
Cod sursa(job #492609)
#include<cstdio>
const int N=1<<10;
short int f[27],sus[N][N][27],st[N][N][27];
int nr,n,m;
char a[N][N],v[N][N];
void read()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d\n",&n,&m);
for(int i=1;i<=n;i++)
gets(a[i]+1);
for(int i=1;i<=m;i++)
gets(v[i]+1);
}
void copy(short int a[27],short int b[27])
{
for(int i=1;i<=26;i++)
a[i]=b[i];
}
void copyi(int a[27],int b[27])
{
for(int i=1;i<=26;i++)
a[i]=b[i];
}
void init_mat()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
copy(sus[i][j],sus[i-1][j]);
sus[i][j][a[i][j]-'a'+1]++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
copy(st[i][j],st[i][j-1]);
st[i][j][a[i][j]-'a'+1]++;
}
}
void getf()
{
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
f[v[i][j]-'a'+1]++;
}
void solve()
{
int fr[27],afr[27];
for(int i=0;i<=26;i++)
fr[i]=afr[i]=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
fr[a[i][j]-'a'+1]++;
for(int i=m;i<=n;i++)
{
copyi(afr,fr);
for(int j=m;j<=n;j++)
{
bool ok=true;
for(int k=1;k<=26;k++)
if(fr[k]!=f[k])
{
ok=false;
break;
}
if(ok)
nr++;
for(int k=1;k<=26;k++)
fr[k]+=(sus[i][j+1][k]-sus[i-m][j+1][k])-(sus[i][j+1-m][k]-sus[i-m][j+1-m][k]);
}
copyi(fr,afr);
for(int k=1;k<=26;k++)
fr[k]+=st[i+1][m][k]-st[i+1-m][m][k];
}
}
int main()
{
read();
init_mat();
getf();
solve();
printf("%d",nr);
return 0;
}