Cod sursa(job #3308943)

Utilizator Lex._.Lex Guiman Lex._. Data 30 august 2025 10:48:23
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#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;
}