Pagini recente » Cod sursa (job #423888) | Cod sursa (job #1066167) | Cod sursa (job #93240) | Cod sursa (job #1107878) | Cod sursa (job #1824959)
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const string name = "matrix",
in_file = name + ".in",
out_file = name + ".out";
ifstream fin(in_file);
ofstream fout(out_file);
const int MAX = 1e3 + 5, SIGMA = 26;
int n, m;
int matrix[MAX][MAX];
int cnt[SIGMA];
int dp[MAX][MAX];
bool ok[MAX][MAX];
int main() {
fin >> n >> m;
string row;
for (int i = 1; i <= n; i++) {
fin >> row;
for (int j = 0; j < n; j++) {
matrix[i][j + 1] = row[j] - 'a';
}
}
for (int i = 0; i < m; i++) {
fin >> row;
for (char letter : row) {
cnt[letter - 'a']++;
}
}
for (int letter = 0; letter < SIGMA; letter++) {
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];
if (matrix[i][j] == letter) {
dp[i][j]++;
}
}
}
for (int i = m; i <= n; i++) {
for (int j = m; j <= n; j++) {
int x1 = i - m, y1 = j - m;
if (dp[i][j] + dp[x1][y1] - dp[x1][j] - dp[i][y1] != cnt[letter]) {
ok[i][j] = 1;
}
}
}
}
int cnt = 0;
for (int i = m; i <= n; i++) {
for (int j = m; j <= n; j++) {
cnt += (1 - ok[i][j]);
}
}
fout << cnt;
return 0;
}