Cod sursa(job #1065595)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 23 decembrie 2013 14:59:36
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f=fopen("matrix.in","r");
FILE *g=fopen("matrix.out","w");
int fr[300],m,n,L,ap[1011][1011],nr;
char ch,a[1011][1011],s[1011];
int ok[1011][1011];

int main(void){
    register int i,j;

    fscanf(f,"%d %d\n",&m,&n);
    for(i=1;i<=m;i++){
        fscanf(f,"%s",a[i]+1);
    }
    for(i=1;i<=n;i++){
        fscanf(f,"%s",s+1);
        L=strlen(s+1);
        for(j=1;j<=L;j++)
            fr[s[j]]++;
    }

    for(ch='a';ch<='z';ch++){
        for(i=1;i<=m;i++)
            for(j=1;j<=m;j++){
                ap[i][j]=0,ap[i][j]=ap[i][j-1]+ap[i-1][j]-ap[i-1][j-1]+(a[i][j]==ch?1:0);
                if(i>=n && j>=n)
                    if(ap[i][j]+ap[i-n][j-n]-ap[i-n][j]-ap[i][j-n]==fr[ch])
                        ok[i][j]=1;
            }
    }
    nr=0;
    for(i=m;i>=n;i--){
        for(j=m;j>=n;j--){
            nr+=ok[i][j];
        }
    }
    fprintf(g,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}