Pagini recente » Cod sursa (job #1973105) | Cod sursa (job #2297950) | Cod sursa (job #3144656) | Cod sursa (job #107651) | Cod sursa (job #76234)
Cod sursa(job #76234)
# include <stdio.h>
const long int MAXL=26;
long int atli(char a) {return (long int)a-(long int)'a'+1;}
typedef long int SET[MAXL+1];
long int n,m;
const long int MAXN=1000; //1000
char om[MAXN+10][MAXN+10];
char vi[MAXN+10][MAXN+10];
SET seta[MAXN+1][MAXN+1],setr[MAXN+1][MAXN+1],setd[MAXN+1],settar;
void citire()
{
FILE *f=fopen("matrix.in","r");
fscanf(f,"%ld%ld",&n,&m);
char s[10000];
fgets(s,10000,f);
long int i,j;
for (i=1;i<=n;i++)
fgets(om[i]+1,1000,f);
for (i=1;i<=m;i++)
fgets(vi[i]+1,1000,f);
fclose(f);
}
void aduna(SET &a, SET b, long int sgn) {long int i;for (i=1;i<=MAXL;i++) a[i]+=sgn*b[i];}
int egal(SET a, SET b) {long int i;for (i=1;i<=MAXL;i++) if (a[i]!=b[i]) return 0; return 1;}
void scrie(long int sol)
{
FILE *g=fopen("matrix.out","w");
fprintf(g,"%ld\n",sol);
fcloseall();
}
void calculeaza()
{
//init setd,setr
long int i,j;
for (i=n;i>=1;i--)
for (j=n;j>=1;j--)
{
setr[i][j][atli(om[i][j])]++;
if (i<=n-m+1) setd[j][atli(om[i][j])]++;
if (j+1<=n) aduna(setr[i][j],setr[i][j+1],1);
if (j+m<=n) aduna(setr[i][j],setr[i][j+m],-1);
}
//init settar
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
settar[atli(vi[i][j])]++;
for (j=n;j>=n-m+1;j--)
aduna(seta[n-m+1][n-m+1],setd[j],1);
for (i=n-m+1;i>=1;i--)
for (j=n-m+1;j>=1;j--)
if (i==n-m+1)
{
if (j<n-m+1)
{
aduna(seta[i][j],seta[i][j+1],1);
aduna(seta[i][j],setd[j],1);
aduna(seta[i][j],setd[j+m],-1);
}
}
else
{
aduna(seta[i][j],seta[i+1][j],1);
aduna(seta[i][j],setr[i][j],1);
aduna(seta[i][j],setr[i+m][j],-1);
}
long int sol=0;
for (i=1;i<=n-m+1;i++)
for (j=1;j<=n-m+1;j++)
if (egal(seta[i][j],settar)) sol++;
scrie(sol);
}
int main()
{
citire();
calculeaza();
return 0;
}