Pagini recente » Cod sursa (job #2611422) | Cod sursa (job #627556) | Cod sursa (job #324862) | Cod sursa (job #2909404) | Cod sursa (job #2970392)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
vector <int> v[1001][26];
int fr[1001][26];
int n, X1, Y1, X2, Y2, res[26], f[26];
struct nod {
int fr[26] = { 0 };
};
int main()
{
int aux;
fin >> n >> aux;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
char c;
fin >> c;
v[i][c - 'a'].push_back(j);
}
for (int i = 1; i <= aux; i++)
for (int j = 1; j <= aux; j++)
{
char c;
fin >> c;
res[c - 'a']++;
}
int cnt = 0;
for (int i = 1; i <= n - aux + 1; i++)
{
for (short k = 0; k < 26; k++)
f[k] = 0;
for (int j = 1; j < aux; j++)
{
for (short k = 0; k < 26; k++)
{
fr[j][k] = 0;
int l = 0, r = v[j][k].size() - 1, poz1 = -1, poz2;
while (l <= r)
{
int m = (l + r) >> 1;
if (v[j][k][m] >= i)
{
poz1 = m;
r = m - 1;
}
else
l = m + 1;
}
if (poz1 == -1 || v[j][k][poz1] > i + aux - 1)
continue;
l = poz1, r = v[j][k].size() - 1;
while (l <= r)
{
int m = (l + r) >> 1;
if (v[j][k][m] <= i + aux - 1)
{
poz2 = m;
l = m + 1;
}
else
r = m - 1;
}
fr[j][k] = poz2 - poz1 + 1;
f[k] += poz2 - poz1 + 1;
}
}
for (int j = aux; j <= n; j++)
{
bool ok = true;
for (short k = 0; k < 26; k++)
{
int l = 0, r = v[j][k].size() - 1, poz1 = -1, poz2;
while (l <= r)
{
int m = (l + r) >> 1;
if (v[j][k][m] >= i)
{
poz1 = m;
r = m - 1;
}
else
l = m + 1;
}
if (poz1 == -1 || v[j][k][poz1] > i + aux - 1)
continue;
l = poz1, r = v[j][k].size() - 1;
while (l <= r)
{
int m = (l + r) >> 1;
if (v[j][k][m] <= i + aux - 1)
{
poz2 = m;
l = m + 1;
}
else
r = m - 1;
}
fr[j][k] = poz2 - poz1 + 1;
f[k] += poz2 - poz1 + 1;
f[k] -= fr[j - aux][k];
ok &= (f[k] == res[k]);
}
if (ok)
cnt++;
}
}
fout << cnt;
return 0;
}