Pagini recente » Cod sursa (job #1082918) | Cod sursa (job #287411) | Cod sursa (job #1484774) | Cod sursa (job #2354943) | Cod sursa (job #557048)
Cod sursa(job #557048)
# include <cstdio>
const char *FIN = "matrix.in", *FOU = "matrix.out" ;
const int MAX = 1005, SG = 26 ;
bool sol[MAX][MAX] ;
char S[MAX][MAX] ;
int dp[MAX][MAX] ;
int F[SG] ;
int N, M ;
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 ;
}
}
int sl = ( N - M + 1 ) * ( N - M + 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] ;
sol[i][j] ? 0 : --sl ;
}
}
}
}
fprintf ( fopen ( FOU, "w" ), "%d", sl ) ;
}