Cod sursa(job #2712435)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 25 februarie 2021 19:18:21
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e3 + 3;
char a[NMAX][NMAX], c;
int N, M, dp[NMAX][NMAX], freq[32], ans;
bool ok[NMAX][NMAX];

int sum(int x1, int y1, int x2, int y2) {
    return dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
}

int main(){
    fin >> N >> M;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j) {
            fin >> a[i][j];
            ok[i][j] = true;
        }
    for(int i = 1; i <= M; ++i)
        for(int j = 1; j <= M; ++j) {
            fin >> c;
            ++freq[c - 'a'];
        }
    for(char ch = 'a'; ch < 'z'; ++ch){
        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] == ch);
        for(int i = 1; i <= N - M + 1; ++i)
            for(int j = 1; j <= N - M + 1; ++j)
                if(sum(i, j, i + M - 1, j + M - 1) != freq[ch - 'a'])
                    ok[i][j] = false;
    }
    for(int i = 1; i <= N - M + 1; ++i)
        for(int j = 1; j <= N - M + 1; ++j)
            ans += ok[i][j];
    fout << ans;
}