Pagini recente » Cod sursa (job #1879583) | Cod sursa (job #2022535) | Cod sursa (job #1540280) | Cod sursa (job #972786) | Cod sursa (job #2120080)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("matrix.in");
ofstream out("matrix.out");
const int maxn = 1005;
int fr[maxn][maxn][30];
int M[maxn][maxn];
int A[maxn][maxn];
int aux[30];
int ap[30];
int n, m;
void suma(int x1, int y1, int x2, int y2)
{
for(int i = 0; i < 26; i++)
aux[i] = fr[x2][y2][i] - fr[x2][y1 - 1][i] - fr[x1 - 1][y2][i] + fr[x1 - 1][y1 - 1][i];
}
int verif(int x, int y)
{
suma(x - m + 1, y - m + 1, x, y);
for(int i = 0; i < 26; i++)
if(aux[i] != ap[i])
return 0;
return 1;
}
int main()
{
in >> n >> m;
for(int i = 1; i <= n; i++)
{
string s;
in >> s;
for(int j = 0; j < n; j++)
M[i][j + 1] = s[j] - 'a';
}
for(int i = 1; i <= m; i++)
{
string s;
in >> s;
for(int j = 0; j < m; j++)
{
A[i][j + 1] = s[j] - 'a';
ap[s[j] - 'a']++;
}
}
/*
for(int i = 1; i <= n; i++, cerr << "\n")
for(int j = 1; j <= n; j++)
cerr << M[i][j] << " ";
cerr << "\n";
*/
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
for(int alpha = 0; alpha < 26; alpha++)
{
int p = M[i][j];
fr[i][j][alpha] = fr[i - 1][j][alpha] + fr[i][j - 1][alpha] - fr[i - 1][j - 1][alpha] + (p == alpha);
}
}
}
/*
for(int i = 1; i <= n; i++, cerr << "\n")
for(int j = 1; j <= n; j++)
cerr << fr[i][j][0] << " ";
*/
int nr = 0;
for(int i = m; i <= n; i++)
for(int j = m; j <= n; j++)
if(verif(i, j))
nr++;
out << nr << "\n";
return 0;
}