Cod sursa(job #899725)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 28 februarie 2013 15:57:40
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 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;
}