Pagini recente » Cod sursa (job #343835) | Cod sursa (job #2370178) | Cod sursa (job #1593186) | Cod sursa (job #1051381) | Cod sursa (job #385467)
Cod sursa(job #385467)
#include <cstdio>
#include <cstring>
#define file_in "matrix.in"
#define file_out "matrix.out"
#define Nmax 1010
int n,m,i,j,sol,k,l,ii,jj;
int f[27];
char s[Nmax];
int frecv[27];
char a[Nmax][Nmax];
int T[Nmax][Nmax];
int main()
{
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d\n", &n, &m);
for (i=1;i<=n;++i)
{
fgets(s,Nmax,stdin);
for (j=0;j<n;++j)
a[i][j+1]=s[j];
}
memset(frecv,0,sizeof(frecv));
for (i=0;i<m;++i)
{
fgets(s,Nmax,stdin);
for (j=0;j<m;++j)
frecv[s[j]-'a']++;
}
if (n<=200)
{
sol=0;
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
{
memset(f,0,sizeof(f));
int ok=0;
for (k=i;k<=i+m-1 && !ok;++k)
for (l=j;l<=j+m-1 && !ok;++l)
{
int x=a[k][l]-'a';
f[x]++;
if (frecv[x]<f[x]) ok=1;
}
if (!ok) sol++;
}
printf("%d\n", sol);
return 0;
}
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
T[i][j]=T[i-1][j]+T[i][j-1]-T[i-1][j-1]+1;
for (i=1;i<=n;++i)
for (j=1;j<=m;++j)
{
int ok=0;
for (k=0;k<26 && !ok;++k)
if (frecv[a[k][l]-'a']!=(T[i][j]-T[i-m][j]-T[i][j-m]+T[i-m][j-m]))
ok=1;
if (!ok) sol++;
}
printf("%d\n", sol);
fclose(stdin);
fclose(stdout);
return 0;
}