Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Diferente pentru utilizator/tudormaxim intre reviziile 32 si 110 | Cod sursa (job #2565362)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "matrix.in" );
ofstream g ( "matrix.out" );
int dp[1002][1002];
bool ok[1002][1002];
char s[1002];
int m1[1002][1002], ap[30];
int main()
{
int n, m;
f >> n >> m;
for ( int i = 1; i <= n; i++ )
{
f >> s;
for ( int j = 0; j < n; j++ )
m1[i][j + 1] = s[j] - 'a';
}
for ( int i = 1; i <= m; i++ )
{
f >> s;
for ( int j = 0; j < m; j++ )
{
int c = s[j] - 'a';
ap[c]++;
}
}
for ( int i = m; i <= n; i++ )
for ( int j = m; j <= n; j++ )
ok[i][j] = 1;
for ( int c = 0; c < 27; c++ )
if ( ap[c] != 0 )
{
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= n; j++ )
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + ( c == ( m1[i][j] - 'a' ) );
if ( i >= m && j >= m )
{
int nr = dp[i][j] - dp[i - m][j] - dp[i][j - m] + dp[i - m][j - m];
if ( nr != ap[c] )
ok[i][j] = 0;
}
}
}
int rez = 0;
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= n; j++ )
if ( ok[i][j] )
rez++;
g << rez;
return 0;
}