Pagini recente » Cod sursa (job #959077) | Cod sursa (job #242913) | Cod sursa (job #1142854) | Cod sursa (job #2368638) | Cod sursa (job #557030)
Cod sursa(job #557030)
# include <bitset>
# include <cstdio>
const char *FIN = "matrix.in", *FOU = "matrix.out" ;
const int MAX = 1005, SG = 26 ;
std :: bitset < MAX > sol[MAX] ;
char S[MAX][MAX] ;
int dp[MAX][MAX] ;
int F[SG] ;
int N, M, sl ;
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] = 1 ;
}
}
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] ) {
sol[i][j] = F[c] == dp[i][j] - dp[i - M][j] - dp[i][j - M] + dp[i - M][j - M] ;
}
}
}
}
for ( int i = M; i <= N; ++i ) {
for ( int j = M; j <= N; ++j ) {
sl += sol[i][j] ;
}
}
fprintf ( fopen ( FOU, "w" ), "%d", sl ) ;
}