Cod sursa(job #1126485)

Utilizator thewildnathNathan Wildenberg thewildnath Data 26 februarie 2014 23:50:27
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>

#define NMAX 1002

int f[NMAX][NMAX][27],fa[2][NMAX][27],fm[27];
char aux[NMAX];

void calc(int n)
{
    int i,j,l;

    for(i=1;i<=n;++i)
    {
        scanf("%s\n",aux+1);
        for(j=1;j<=n;++j)
        {
            for(l=0;l<=25;++l)
                f[i][j][l]=f[i-1][j][l]+f[i][j-1][l]-f[i-1][j-1][l];
            ++f[i][j][aux[j]-'a'];
        }
    }
}

void calc2(int n)
{
    int i,j,l,lin=0;

    for(i=1;i<=n;++i,lin=1-lin)
    {
        scanf("%s\n",aux+1);
        for(j=1;j<=n;++j)
        {
            for(l=0;l<=25;++l)
                fa[lin][j][l]=fa[1-lin][j][l]+fa[lin][j-1][l]-fa[1-lin][j-1][l];
            ++fa[lin][j][aux[j]-'a'];
        }
    }

    for(i=0;i<=25;++i)
        fm[i]=fa[1-lin][n][i];
}

int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    int n,m,i,j,l,sol=0;

    scanf("%d%d\n",&n,&m);

    calc(n);
    calc2(m);


    for(i=m;i<=n;++i)
    {
        for(j=m;j<=n;++j)
        {
            for(l=0;l<=25;++l)
                if(f[i][j][l]-f[i-m][j][l]-f[i][j-m][l]+f[i-m][j-m][l] !=  fm[l])
                    break;
            if(l==26)
                ++sol;
        }
    }

    printf("%d\n",sol);

    return 0;
}