Cod sursa(job #3356282)

Utilizator rares89_Dumitriu Rares rares89_ Data 30 mai 2026 16:29:42
Problema Matrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

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

int m, n;
char a[1005][1005];
int target[26];
int col_cnt[1005][26];
int cur[26];

int main() {
    fin >> m >> n;
    for (int i = 1; i <= m; ++i) {
        fin >> (a[i] + 1);
    }
    
    for (int i = 1; i <= n; ++i) {
        string s;
        fin >> s;
        for (int j = 0; j < n; ++j) {
            target[s[j] - 'a']++;
        }
    }
    
    int ans = 0;
    
    for (int i = 1; i <= m - n + 1; ++i) {
        if (i == 1) {
            for (int j = 1; j <= m; ++j) {
                for (int r = 1; r <= n; ++r) {
                    col_cnt[j][a[r][j] - 'a']++;
                }
            }
        } else {
            for (int j = 1; j <= m; ++j) {
                col_cnt[j][a[i - 1][j] - 'a']--;
                col_cnt[j][a[i + n - 1][j] - 'a']++;
            }
        }
        
        memset(cur, 0, sizeof(cur));
        for (int j = 1; j <= n; ++j) {
            for (int c = 0; c < 26; ++c) {
                cur[c] += col_cnt[j][c];
            }
        }
        
        bool ok = true;
        for (int c = 0; c < 26; ++c) {
            if (cur[c] != target[c]) {
                ok = false;
                break;
            }
        }
        if (ok) ans++;
        
        for (int j = 2; j <= m - n + 1; ++j) {
            for (int c = 0; c < 26; ++c) {
                cur[c] -= col_cnt[j - 1][c];
                cur[c] += col_cnt[j + n - 1][c];
            }
            
            ok = true;
            for (int c = 0; c < 26; ++c) {
                if (cur[c] != target[c]) {
                    ok = false;
                    break;
                }
            }
            if (ok) ans++;
        }
    }
    
    fout << ans << "\n";
    
    fin.close();
    fout.close();
    return 0;
}