Cod sursa(job #3261736)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 7 decembrie 2024 11:43:58
Problema Matrix Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 1001, NR_LET = 26;
int N, M;

struct LetterFr
{
    int arr[NR_LET];

    inline LetterFr& operator= (const LetterFr& rhs)
    {
        for(int i = 0; i < NR_LET; i++)
            arr[i] = rhs.arr[i];
        return *this;
    }

    inline LetterFr operator+ (const LetterFr& rhs)
    {
        LetterFr res = *this;
        for(int i = 0; i < NR_LET; i++)
            res.arr[i] += rhs.arr[i];
        return res;
    }

    inline LetterFr operator+ (const char& rhs)
    {
        LetterFr res = *this;
        res.arr[rhs - 'a']++;
        return res;
    }

    inline LetterFr& operator+= (const char& rhs)
    {
        arr[rhs-'a']++;
        return *this;
    }

    inline LetterFr operator- (const LetterFr& rhs)
    {
        LetterFr res = *this;
        for(int i = 0; i < NR_LET; i++)
            res.arr[i] -= rhs.arr[i];
        return res;
    }

    inline bool operator== (const LetterFr& rhs) const
    {
        for(int i = 0; i < NR_LET; i++)
            if(arr[i] != rhs.arr[i])
                return false;
        return true;
    }

    void Show()
    {
        for(int i = 0; i < 5; i++)
            cerr << (char)('a' + i) << ": " << arr[i] << ", ";
        cerr << '\n';
    }
};

LetterFr match;
LetterFr m[N_MAX][N_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

int main()
{
    SetInput("matrix");

    string str;

    cin >> N >> M;

    for(int i = 1; i <= N; i++)
    {
        cin >> str;
        for(int j = 1; j <= N; j++)
        {
            m[i][j] = m[i-1][j] + m[i][j-1] - m[i-1][j-1] + str[j-1]; /// OBS: str is indexed from 0
            //cerr << i << ' ' << j << '\n';
            //m[i][j].Show();
        }
    }

    for(int i = 1; i <= M; i++)
    {
        cin >> str;
        for(int j = 0; j < M; j++)
            match = match + str[j];
    }

    int ans = 0;
    for(int i = M; i <= N; i++)
        for(int j = M; j <= N; j++)
            if(m[i][j] - m[i-M][j] - m[i][j-M] + m[i-M][j-M] == match)
                ans++;

    cout << ans;

    return 0;
}