Pagini recente » Cod sursa (job #1935273) | Cod sursa (job #1647690) | Cod sursa (job #795981) | Cod sursa (job #2620507) | Cod sursa (job #3161929)
#include <bits/stdc++.h>
using namespace std;
/**
4 2
bbba 0 0 1 0
ccaa => 0 1 0 0
abab 0 1 0 1
baac 1 0 0 2
aa => s = 0+0+1+1=2
bb
aa Y = 0+0+9+9 = 18
dd => X = 0+0+3+3=6
bb s = 1+1+2+2 = 6
cc => sp=1+1+4+4 = 10
*/
ifstream fin("matrix.in");
ofstream fout("matrix.out");
int X, Y, m, cnt;
int s[1002][1002], sp[1002][1002], n;
char a[1002][1002];
int main()
{
int i, j, x, y;
/// citire si formare sume partiale
fin >> n >> m;
for (i = 1; i <= n; i++)
fin >> (a[i] + 1);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
x = a[i][j] - 'a' + 1;
s[i][j] = s[i-1][j]+s[i][j-1]+
x-s[i-1][j-1];
sp[i][j] = sp[i-1][j]+sp[i][j-1]+
x*x-sp[i-1][j-1];
}
X = Y = 0;
for (i = 1; i <= m; i++)
fin >> (a[i] + 1);
for (i = 1; i <= m; i++)
for (j = 1; j <= m; j++)
{
x = a[i][j] - 'a' + 1;
X += x;
Y += x * x;
}
/// contorizare
for (i = m; i <= n; i++)
for (j = m; j <= n; j++)
{
x = s[i][j]-s[i-m][j]-s[i][j-m]
+ s[i-m][j-m];
y = sp[i][j]-sp[i-m][j]-sp[i][j-m]
+ sp[i-m][j-m];
if (x == X && y == Y)
cnt++;
}
fout << cnt << "\n";
return 0;
}