Pagini recente » Cod sursa (job #2845626) | Cod sursa (job #717190) | Cod sursa (job #1634207) | Cod sursa (job #653415) | Cod sursa (job #3277127)
#include <bits/stdc++.h>
std::ifstream fin("matrix.in");
std::ofstream fout("matrix.out");
const int SIZE = 1005;
const int SIGMA = 'z' + 5;
int n, m;
char a[SIZE][SIZE], b[SIZE][SIZE];
// dp[i][j] este folosit pt sume partiale de frecvente de caractere
int dp[SIZE][SIZE];
bool ok[SIZE][SIZE];
int fr[SIGMA];
// ok[i][j] = 1, daca submatricea cu coltul din dreapta jos (i, j) este o "anagrama" a lui B
int64_t max(std::vector<int64_t> v){ return *std::max_element(v.begin(), v.end()); }
int64_t min(std::vector<int64_t> v){ return *std::min_element(v.begin(), v.end()); }
int main()
{
fin >> n >> m;
// prima matrice
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
fin >> a[i][j];
// a doua matrice, cea de cautat
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= m; ++j)
fin >> b[i][j];
// frecventa pe matricea B
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= m; ++j)
fr[b[i][j]]++;
// daca facem sume partiale de frecventa pt fiecare litera (a...z), atunci pt ca o submatrice cu coltul
// de jos in (i, j) sa respecte conditia, ea trebuie sa aiba frecventa buna pt fiecare caracter
//presupunem ca toate submatricele sunt bune si verificam care nu sunt corecte
memset(ok, true, sizeof(ok));
for(char k = 'a'; k <= 'z'; ++k)
{
// sume partiale
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] + (a[i][j] == k);
// verificam frecventa pt fiecare candidat la solutie
for(int i = m; i <= n; ++i)
for(int j = m; j <= n; ++j)
{
int frecv = dp[i][j] - dp[i - m][j] - dp[i][j - m] + dp[i - m][j - m];
if(frecv != fr[k])
ok[i][j] = 0;
}
}
// daca ok[i][j] = 1, atunci avem o submatrice buna
int ans = 0;
for(int i = m; i <= n; ++i)
for(int j = m; j <= n; ++j)
ans += ok[i][j];
fout << ans;
return 0;
}