Cod sursa(job #832697)

Utilizator geniucosOncescu Costin geniucos Data 11 decembrie 2012 08:41:50
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
using namespace std;
int s,i,j,n,m,lit,ap[28],b[1004][1004],dp[1004][1004];
char car,a[1024][1024];
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++)
    gets(a[i]+1);
for(i=1;i<=m;i++)
{
    for(j=1;j<=m;j++)
    {
        scanf("%c",&car);
        ap[car-'a']++;
    }
    scanf("\n");
}
for(i=m;i<=n;i++)
    for(j=m;j<=n;j++)
        dp[i][j]=1;
for(lit=0;lit<26;lit++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+(a[i][j]-'a'==lit);
            if(i>=m&&j>=m&&b[i][j]-b[i-m][j]-b[i][j-m]+b[i-m][j-m]!=ap[lit])
                dp[i][j]=0;
        }
for(i=m;i<=n;i++)
    for(j=m;j<=n;j++)
        s=s+dp[i][j];
printf("%d\n",s);
return 0;
}