Pagini recente » Cod sursa (job #2650634) | Cod sursa (job #2688286) | Cod sursa (job #2596298) | Cod sursa (job #2779317) | Cod sursa (job #557023)
Cod sursa(job #557023)
# include <cstdio>
const char *FIN = "matrix.in", *FOU = "matrix.out" ;
const int MAX = 1105, 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 ) ;
}