Cod sursa(job #3352703)

Utilizator iccjocIoan CHELARU iccjoc Data 30 aprilie 2026 17:05:10
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;

char mat[1005][1005];
vector<int> f(256, 0);
vector<int> c(256, 0);
unsigned short sp[26][1005][1005];

int main()
{
    ifstream cin("matrix.in");
    ofstream cout("matrix.out");
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> mat[i][j];
        }
    }

    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            char x;
            cin >> x;
            f[(int)(x)]++;
        }
    }


    // for(int i = 'a'; i <= 'd'; i++)
    // {
    //     cout << f[i] << " ";
    // }
    // cout << "\n";

    for(int k = 0; k < 26; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                sp[k][i][j] = sp[k][i - 1][j] + sp[k][i][j - 1] - sp[k][i - 1][j - 1] + (mat[i][j] == (char)(k + 'a'));
            }
        }
    }

    int cnt = 0;

    for(int i = 1; i <= n - m + 1; i++)
    {
        for(int j = 1; j <= n - m + 1; j++)
        {
            for(int k = 0; k < 26; k++)
            {
                c[(int)(k + 'a')] = sp[k][i + m - 1][j + m - 1] - sp[k][i - 1][j + m - 1] - sp[k][i + m - 1][j - 1] + sp[k][i - 1][j - 1];
            }
            if(c == f)
            {
                // cout << i << " " << j << "\n";
                cnt++;
            }
            c.assign(256, 0);
        }
    }

    cout << cnt;
}