Cod sursa(job #211205)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 1 octombrie 2008 12:20:31
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#define sigma 25
long n,m,i,j,k,s,total,f[26],a[1001][1024];
char ch[1001][1024],g[1024];
bool ok[1001][1024];
int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%ld %ld\n",&m,&n);
    for (i=0;i<m;++i)
        scanf("%s",ch[i]);
    for (i=0;i<n;++i){
        scanf("%s",g);
        for (j=0;j<n;++j)
            f[g[j]-'a']++;
    }
    for (k=0;k<sigma;++k){
        //preprocesare
        for (i=1;i<=m;++i)
            for (j=1;j<=m;++j){
                a[i][j]=a[i][j-1]-a[i-1][j-1]+a[i-1][j];
                if (ch[i-1][j-1]=='a'+k)a[i][j]++;
            }
        for (i=n;i<=m;++i)
            for (j=n;j<=m;++j)if (!ok[i][j]){
                s=a[i][j]-a[i][j-n]-a[i-n][j]+a[i-n][j-n];
                if (s!=f[k])ok[i][j]=1;
            }
    }
    total=0;
    for (i=n;i<=m;++i)
        for (j=n;j<=m;++j)
            if (!ok[i][j])total++;
    printf("%ld\n",total);
return 0;
}