Pagini recente » Cod sursa (job #1904692) | Cod sursa (job #3330086) | Cod sursa (job #2360018) | Cod sursa (job #1617529) | Cod sursa (job #3308943)
#include <bits/stdc++.h>
#define NMAX 1001
using namespace std;
ifstream in("matrix.in");
ofstream out("matrix.out");
int m, n;
char matrice[NMAX][NMAX]; ///matricea de m x m
int sp[NMAX][NMAX]; ///sume partiale pentru frecventa fiecarei litere
int fr_n[26]; ///frecventa fiecarei litere in matricea virusului
bool egale[NMAX][NMAX]; ///1 daca frecventele literelor in acea celula sunt egale cu frecventele din matricea virusului si 0 daca nu sunt
int main()
{
in >> m >> n;
for(int i=1; i<=m; i++) ///citim matricea de m x m
{
for(int j=1; j<=m; j++)
{
in >> matrice[i][j];
if(i>=n && j>=n)
egale[i][j]=1;
}
}
for(int i=1; i<=n; i++) ///citim matricea virusului
{
for(int j=1; j<=n; j++)
{
char litera;
in >> litera;
fr_n[litera-'a']++;
}
}
for(int litera=0; litera<26; litera++)
{
for(int i=1; i<=m; i++) ///calculam sumele partiale pentru fiecare litera
{
for(int j=1; j<=m; j++)
{
sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1];
if(matrice[i][j]-'a'==litera)
sp[i][j]++;
}
}
for(int i=n; i<=m; i++)
{
for(int j=n; j<=m; j++)
{
if(sp[i][j]-sp[i-n][j]-sp[i][j-n]+sp[i-n][j-n] != fr_n[litera]) ///daca frecventa literei in submatricea de coordonate (i-n+1, j-n+1) si (i, j) este diferita de frecventa literei in fr_n
egale[i][j]=0;
}
}
}
int nr_aparitii=0; ///numarul de aparitii cerut
for(int i=n; i<=m; i++)
{
for(int j=n; j<=m; j++)
{
if(egale[i][j]==1) nr_aparitii++;
}
}
out << nr_aparitii;
return 0;
}