Pagini recente » Cod sursa (job #483223) | Cod sursa (job #3252455) | Cod sursa (job #2503102) | Cod sursa (job #3219333) | Cod sursa (job #774273)
Cod sursa(job #774273)
#include<stdio.h>
FILE *f = fopen("matrix.in","r");
FILE *g = fopen("matrix.out","w");
#define MaxM 1001
#define sh short int
#define MaxSig 26
int N,M,Sol;
char A[MaxM][MaxM],B[MaxM][MaxM];
int C[MaxM][MaxM][MaxSig];
int Best[MaxSig],BestM[MaxSig],Comp[MaxSig];
void citire(void)
{
fscanf(f,"%d %d\n",&M,&N);
for(int i=1;i<=M;i++)
fgets(A[i],sizeof(A[i]),f);
for(int i=1;i<=N;i++)
fgets(B[i],sizeof(B[i]),f);
}
void Preprocesare(void)
{
for(int i=1;i<=N;i++)
for(int j=0;j<N;j++)
++ Comp[B[i][j]-'a'];
for(int i=0;i<M;i++)
{
for(int j=1;j<=N;j++)
++ C[1][i][A[j][i]-'a'];
for(int j=2;j<=M-N+1;j++)
{
-- C[j][i][A[j-1][i]-'a'];
++ C[j][i][A[j+N-1][i]-'a'];
for(int k=0;k<=25;k++)
C[j][i][k] += C[j-1][i][k];
}
}
}
inline int Verif(void)
{
for(int i=0;i<25;i++)
if(Best[i] != Comp[i])
return 0;
return 1;
}
void Rezolvare(void)
{
Preprocesare();
for(int i=1;i<=N;i++)
for(int j=0;j<N;j++)
++ BestM[A[i][j]-'a'],++ Best[A[i][j]-'a'];
for(int i=1;i<=M-N+1;i++)
{
for(int j=0;j<=M-N;j++)
{
Sol += Verif();
if(j<M-N)
for(int k=0;k<=25;k++)
Best[k] += (-C[i][j][k]+C[i][j+N][k]);
}
for(int k=0;k<N;k++)
-- BestM[A[i][k]-'a'], ++BestM[A[i+N][k]-'a'];
for(int k=0;k<25;k++)
Best[k] = BestM[k];
}
}
int main()
{
citire();
Rezolvare();
fprintf(g,"%d\n",Sol);
}