Pagini recente » Borderou de evaluare (job #1230690) | Cod sursa (job #270243)
Cod sursa(job #270243)
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, i, j, v[1010][1010], x[1010][1010], col[1010][30];
char s[1010];
int curr[30], nd[30], sol;
inline bool egal(int a[], int b[]) {
for (int i = 1; i <= 27; i++)
if (a[i] != b[i])
return false;
return true;
}
inline void scad(int a[], int b[]) {
for (int i = 1; i <= 27; i++)
a[i] -= b[i];
}
inline void add(int a[], int b[]) {
for (int i = 1; i <= 27; i++)
a[i] += b[i];
}
int main() {
freopen("matrix.in", "r", stdin);
freopen("matrix.out", "w", stdout);
scanf("%d %d ", &n, &m);
for (i = 1; i <= n; i++) {
fgets(s, 1010, stdin);
for (j = 0; j < n; j++)
v[i][j + 1] = s[j] - 'a' + 1;
}
for (i = 1; i <= m; i++) {
fgets(s, 1010, stdin);
for (j = 0; j < m; j++)
x[i][j + 1] = s[j] - 'a' + 1;
}
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
col[j][v[i][j]]++;
for (i = 1; i <= m; i++)
for (j = 1; j <= m; j++) {
nd[x[i][j]]++;
curr[v[i][j]]++;
}
for (i = m; i <= n; i++) {
//mai intai fac jmenu pe coloane apoi recalculez col[i]
for (j = m; j <= n; j++) {
if (egal(curr, nd))
sol++;
scad(curr, col[j - m + 1]);
add(curr, col[j + 1]);
}
for (j = 1; j <= n; j++) {
col[j][v[i - m + 1][j]]--;
col[j][v[i + 1][j]]++;
}
memset(curr, 0, sizeof(curr));
for (j = 1; j <= m; j++)
add(curr, col[j]);
}
printf("%d\n", sol);
return 0;
}