Cod sursa(job #854300)

Utilizator ericptsStavarache Petru Eric ericpts Data 13 ianuarie 2013 12:02:55
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
using namespace std;
int n,m;
char om[1001][1001];
bool ok[1001][1001];
int d[1001][1001];
char virus[1001];
int ap['z'+5];
char *p;
int main()
{

    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);

    int i,j;
    char let;

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

    for( i=1 ; i <= n ; ++ i)
        gets(om[i]+1);
    for( i=1 ; i <= m ; ++ i)
    {
        gets(virus);

        p = virus;

        while(*p != '\n' && *p)
            ++ap[*(p++)];
    }
    for(i=m;i<=n;++i)
        for(j=m;j<=n;++j)
            ok[i][j] = 1;

    for(let = 'a'; let <= 'z'; ++ let)
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
    {
        d[i][j] = d[i-1][j] + d[i][j-1] - d[i-1][j-1];
        if(om[i][j] == let)
            ++d[i][j];
        if(ok[i][j])
        {
            if(d[i][j] - d[i-m][j] - d[i][j-m] + d[i-m][j-m] != ap[let])
                ok[i][j] = 0;
        }
    }
    int show = 0;
    for(i=m;i<=n;++i)
        for(j=m;j<=n;++j)
            if(ok[i][j])
                ++show;
    printf("%d\n",show);

    return 0;
}