Cod sursa(job #2986111)

Utilizator DooMeDCristian Alexutan DooMeD Data 27 februarie 2023 18:56:34
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e3;
const int SIGMA = 26;

char a[nmax+5][nmax+5], b[nmax+5][nmax+5];

int vf[SIGMA];
bool ok[nmax+5][nmax+5][SIGMA];

int ret[nmax+5][nmax+5];

int main() {
    ifstream f("matrix.in");
    ofstream g("matrix.out");

    int n, m; f >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f >> a[i][j];
    for(int i=1; i<=m; i++)
        for(int j=1; j<=m; j++) {
            f >> b[i][j];
            vf[b[i][j] - 'a']++;
        }

    for(int k=0; k<SIGMA; k++) {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                ret[i][j] = (a[i][j]-'a'==k) + ret[i-1][j] + ret[i][j-1] - ret[i-1][j-1];

        for(int i=m; i<=n; i++)
            for(int j=m; j<=n; j++) 
                if(ret[i][j] - ret[i-m][j] - ret[i][j-m] + ret[i-m][j-m] == vf[k])
                    ok[i][j][k] = true;
    }

    int ans = 0;
    for(int i=m; i<=n; i++)
        for(int j=m; j<=n; j++) {
            bool w = 1;
            for(int k=0; k<SIGMA; k++) w &= ok[i][j][k];
            ans += w;
        }
    g << ans;
    return 0;
}