Cod sursa(job #655033)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 31 decembrie 2011 18:32:15
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>

bool b[1005][1005];
char a[1005][1005],x[1005];
int v[26],s[1005][1005];

int main()
{
    int n,m,i,j,k,sol=0;

    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d %d\n",&n,&m);

    for (i=1;i<=n;++i)
        fgets(a[i]+1,1002,stdin);

    for (i=1;i<=m;++i)
    {
        fgets(x,1002,stdin);
        for (j=0;j<m;++j)
            ++v[x[j]-'a'];
    }

    for (i=0;i<25;++i)
    {
        for (j=1;j<=n;++j)
            for (k=1;k<=n;++k)
                s[j][k]=s[j-1][k]+s[j][k-1]-s[j-1][k-1]+(a[j][k]-'a'==i);
        for (j=m;j<=n;++j)
            for (k=m;k<=n;++k)
                if (v[i]!=s[j][k]-s[j][k-m]-s[j-m][k]+s[j-m][k-m])
                    b[j][k]=1;
    }

    for (i=m;i<=n;++i)
        for (j=m;j<=n;++j)
            if (!b[i][j])
                ++sol;

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

    return 0;
}