Cod sursa(job #904252)

Utilizator ion824Ion Ureche ion824 Data 3 martie 2013 23:12:17
Problema Matrix Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<cstdio>
const int NM=1002;
char a[NM][NM],b[NM][NM];
int c0[27],l0[27],t[27],g[27],t0[27],NR;
int d[NM][27],C[NM][27];

void verify(){
     for(int i=0;i<26;++i)if(t[i]!=g[i])return;
     ++NR;
     }

int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);  
    int N,M,i,j,q,k;
    scanf("%d%d\n",&N,&M);
    for(i=1;i<=N;++i)scanf("%s",a[i]);
    for(i=1;i<=M;++i)scanf("%s",b[i]);
    for(i=1;i<=M;++i)
      for(j=0;j<M;++j){ g[b[i][j]-'a']++; t[a[i][j]-'a']++; }
    for(i=1;i<=N;++i)
      for(j=0;j<M;++j){ d[i][a[i][j]-'a']++; C[i-1][a[i][j]-'a']++; }
    
    for(i=0;i<26;++i) t0[i]=t[i]; 
    
    for(i=1;i<=N-M+1;++i)
    {
      if(i!=1){
               for(q=0;q<26;++q){ t[q]=(t0[q]+d[i+M-1][q]-d[i-1][q]); t0[q]=t[q]; }
               for(q=0;q<N;++q){ C[q][a[i+M-1][q]-'a']++; C[q][a[i-1][q]-'a']--; }
               }
      verify();
      for(j=M;j<N;++j)
        {
          for(k=0;k<26;++k) t[k]+=(C[j][k]-C[j-M][k]); 
          verify();                 
        }
    }
    
    printf("%d",NR);         
  return 0;
}