Cod sursa(job #557012)

Utilizator SpiderManSimoiu Robert SpiderMan Data 16 martie 2011 13:44:07
Problema Matrix Scor 0
Compilator cpp Status done
Runda matrice_ Marime 1.4 kb
# include <cstdio>

const char *FIN = "matrix.in", *FOU = "matrix.out" ;
const int MAX = 1005, SG = 26 ;

char S[MAX][MAX] ;
int dp[MAX][MAX] ;
int F[SG] ;
int N, M, sl ;
unsigned sol[MAX][MAX >> 5] ;

int main ( void ) {
    freopen ( FIN, "r", stdin ) ;

    scanf ( "%d %d", &N, &M ) ;
    for ( int i = 1; i <= N; ++i ) {
        scanf ( "%s", S[i] + 1 ) ;
    }
    for ( int i = 1; i <= M; ++i ) {
        scanf ( "%s", S[0] + 1 ) ;
        for ( int j = 1; j <= M; ++j ) {
            ++F[ S[0][j] - 'a' ] ;
        }
    }
    for ( int i = M; i <= N; ++i ) {
        for ( int j = M; j <= N; ++j ) {
            sol[i][j >> 5] |= ( 1 << ( j & 31 ) ) ;
        }
    }
    for ( int c = 0; c < SG; ++c ) {
        for ( int i = 1; i <= N; ++i ) {
            for ( int j = 1; j <= N; ++j ) {
                dp[i][j] = ( c + 'a' == S[i][j] ) + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] ;
                if ( i >= M && j >= M && sol[i][j] ) {
                    if ( F[c] == dp[i][j] - dp[i - M][j] - dp[i][j - M] + dp[i - M][j - M] )
                        sol[i][j >> 5] ^= ( 1 << ( j & 31 ) ) ;
                }
            }
        }
    }

    for ( int i = M; i <= N; ++i ) {
        for ( int j = M; j <= N; ++j ) {
            if ( sol[i][j >> 5] & ( 1 << ( j & 31 ) ) )
                sl += 1 ;
        }
    }
    fprintf ( fopen ( FOU, "w" ), "%d", sl ) ;
}