Cod sursa(job #3340161)

Utilizator PopRadGabPopescu Radu Gabriel PopRadGab Data 12 februarie 2026 12:45:38
Problema Matrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

int n,m;

char fr[256];
int D[1001][1001]; // o sa- o construim la verif fiecarei litere
char A[1001][1001],B[1001][1001];


int main(){
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    fin>>n>>m;
    // aici verif. fiecare pozitie (i,j)
    vector<vector<bool>> ok(n+1,vector<bool> (n+1),true);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fin>>A[i][j];
    // pentru faptul ca se pot dezordona elem. din B[i][j] putem calcula frecventele elem.
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++){
            fin>>B[i][j];
            fr[B[i][j]]++;
        }

        for(char ch='a';ch<='z';ch++){

            // metoda rapida de rezolvare sunt sumele partiale pe matrice pt a verifica frecventa
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    D[i][j]=((A[i][j]==ch) ? 1 : 0) + D[i-1][j]+D[i][j-1]-D[i-1][j-1];
            // verif. practica
            for(int i=m;i<=n;i++)
                for(int j=m;j<=n;j++)
                    if(D[i][j]-D[i-m][j]-D[i][j-m]+D[i-m][j-m]!=fr[ch])
                        ok[i][j]=false;
        }

        int sol=0;
        for(int i=m;i<=n;i++)
            for(int j=m;j<=n;j++)
                sol+=(int)ok[i][j];
    fout<<sol;
    return 0;
}