Pagini recente » Cod sursa (job #1331999) | Cod sursa (job #2527590) | Cod sursa (job #1398364) | Cod sursa (job #3138623) | Cod sursa (job #42959)
Cod sursa(job #42959)
#include<stdio.h>
#include<fstream.h>
#define nmax 1002
long m,n,v[28],t[nmax][nmax];
int long t1[nmax][nmax];
char c[nmax][nmax];
void citire()
{char d;
int i,j;
freopen("matrix.in","r",stdin);
scanf("%d%d",&m,&n);
fgets(c[0],nmax,stdin);
for(i=0;i<m;i++)
{
fgets(c[i],nmax,stdin);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%c ",&d);
v[d-'a']++;
}
}
void init(char s)
{int i,j;
//memset(t,0,sizeof(t));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{if(c[i-1][j-1]==s)
t[1][1]++;
if(c[i][j-1]==s)
t[2][1]++;
}
if(t[1][1]==v[s-'a'])
t1[1][1]|=(long)1<<(s-'a');
if(t[2][1]==v[s-'a'])
t1[2][1]|=(long)1<<(s-'a');
for(i=2;i<=m-n+1;i++)
{t[1][i]=t[1][i-1];
for(j=1;j<=n;j++)
{if(c[j-1][i-2]==s)
t[1][i]--;
if(c[j-1][i+n-2]==s)
t[1][i]++;
}
if(t[1][i]==v[s-'a'])
t1[1][i]|=(long)1<<s-'a';
}
}
void rezolva(char s)
{int i,j;
memset(t,0,sizeof(t));
init(s);
for(i=2;i<=m-n+1;i++)
for(j=(i!=2)?1:2;j<=m-n+1;j++)
{t[i][j]=t[i-1][j]+t[i][j-1]-t[i-1][j-1];
if(c[i-2][j-2]==s)
t[i][j]++;
if(c[i+n-2][j+n-2]==s)
t[i][j]++;
if(c[i-2][j+n-2]==s)
t[i][j]--;
if(c[i+n-2][j-2]==s)
t[i][j]--;
if(t[i][j]==v[s-'a']) t1[i][j]|=(long)1<<s-'a';
}
}
long numara()
{int i,j,nr=0;
for(i=1;i<=m-n+1;i++)
for(j=1;j<=m-n+1;j++)
if(t1[i][j]==((long)1<<'z'-'a'+1)-1)
nr++;
return nr;
}
int main()
{char c;
citire();
for(c='a';c<='z';c++)
rezolva(c);
freopen("matrix.out","w",stdout);
printf("%ld",numara());
fclose(stdout);
return 0;
}