Pagini recente » Cod sursa (job #2765753) | Cod sursa (job #1061452)
#include <fstream>
using namespace std;
const int MAX_N = 1002;
const int SIGMA = 26;
int N, M, sol;
int freq[SIGMA], dp[MAX_N][MAX_N];
char s[MAX_N], A[MAX_N][MAX_N];
bool OK[MAX_N][MAX_N];
int main() {
ifstream f("matrix.in");
ofstream g("matrix.out");
f >> N >> M;
for(int i = 1; i <= N; ++i)
f >> (A[i] + 1);
for(int i = 1; i <= M; ++i) {
f >> s;
for(int j = 0; j < M; ++j)
++freq[s[j] - 'a'];
}
for(int i = M; i <= N; ++i)
for(int j = M; j <= N; ++j)
OK[i][j] = 1;
for(int k = 0; k < SIGMA; ++k) {
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] + ((A[i][j] - 'a') == k);
for(int i = M; i <= N; ++i)
for(int j = M; j <= N; ++j) {
if(OK[i][j] == 0)
continue;
if(freq[k] != dp[i][j] - dp[i - M][j] - dp[i][j - M] + dp[i - M][j - M])
OK[i][j] = 0;
}
}
for(int i = M; i <= N; ++i)
for(int j = M; j <= N; ++j)
sol += OK[i][j];
g << sol << "\n";
f.close();
g.close();
return 0;
}