Cod sursa(job #1734159)

Utilizator silkMarin Dragos silk Data 26 iulie 2016 17:30:13
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include <cstring>
#define NMax 1005
#define DIM 28

char a[NMax][NMax];
char str[NMax];

int col[NMax][DIM];
int temp[DIM];
int ap[DIM];

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

    int i,j,M,N,ans,p;
    char go;

    scanf("%d %d",&M,&N);
    scanf("%c",&go);

    for( i = 1; i <= M; ++i ) fgets( a[i] + 1 , NMax - 1, stdin );

    for( i = 1; i <= N; ++i )
    {
        fgets( str + 1, NMax - 1, stdin );
        for( j = 1; j <= N; ++j )
        ++ap[ str[j] - 'a' + 1 ];
    }

    for( i = 1; i <= M; ++i )
        for( j = 1; j <= N; ++j ) ++col[i][ a[j][i] - 'a' + 1 ];

    for( i = 1; i <= M; ++i ) a[M+1][i] = 'a';

    for( ans = 0, i = 1; i <= M - N + 1; ++i )
    {
        memset(temp,0,sizeof(temp));

        for( j = 1; j <= N; ++j )
            for( p = 1; p <= 26; ++p )
            temp[p] += col[j][p];

        for( p = 1; p <= 26 && temp[p] == ap[p]; ++p );
        if( p > 26 ) ++ans;

        for( j = 2; j <= M - N + 1; ++j )
        {
            for( p = 1; p <= 26; ++p )
            temp[p] -= col[j-1][p];

            for( p = 1; p <= 26; ++p )
            temp[p] += col[j-1+N][p];

            for( p = 1; p <= 26 && temp[p] == ap[p]; ++p );
            if( p > 26 ) ++ans;
       }

        for( j = 1; j <= M; ++j ) --col[j][ a[i][j] - 'a' + 1 ];
        for( j = 1; j <= M; ++j ) ++col[j][ a[ i + N ][j] - 'a' + 1 ];
    }

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



return 0;
}