Pagini recente » Cod sursa (job #910212) | Cod sursa (job #2092973) | Cod sursa (job #2690833) | Cod sursa (job #326456) | Cod sursa (job #1903122)
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
const int NMAX = 1000 + 5;
int freq[NMAX][NMAX][13];
string mat[NMAX];
int freqP[26];
bool ok[NMAX][NMAX];
int main()
{
ifstream cin("matrix.in");
ofstream cout("matrix.out");
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; ++ i) {
cin >> mat[i];
mat[i] = " " + mat[i];
for (int j = 1; j <= N; ++ j)
ok[i][j] = true;
}
string pattern;
for (int i = 1; i <= M; ++ i) {
cin >> pattern;
for (auto it: pattern)
++ freqP[it - 'a'];
}
int ans = 0;
for (int addent = 0; addent < 14; addent += 13) {
for (int i = 1; i <= N; ++ i) {
for (int j = 1; j <= N; ++ j) {
for (int k = 0; k < 13; ++ k)
freq[i][j][k] = freq[i - 1][j][k] - freq[i - 1][j - 1][k] + freq[i][j - 1][k];
if (addent == 0) {
if (mat[i][j] - 'a' < 13)
++ freq[i][j][mat[i][j] - 'a'];
}
else {
if (mat[i][j] - 'a' >= 13)
++ freq[i][j][mat[i][j] - 'a' - 13];
}
}
}
for (int i = 1; i + M - 1 <= N; ++ i)
for (int j = 1; j + M - 1 <= N; ++ j) {
for (int k = 0; k < 13 && ok[i][j]; ++ k) {
int aux = freq[i + M - 1][j + M - 1][k] + freq[i - 1][j - 1][k] -
freq[i + M - 1][j - 1][k] - freq[i - 1][j + M - 1][k];
if (aux != freqP[k + addent])
ok[i][j] = false;
}
if (addent)
ans += ok[i][j];
}
if (!addent)
memset(freq, 0, sizeof freq);
}
cout << ans << '\n';
return 0;
}