Cod sursa(job #2293719)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 1 decembrie 2018 14:50:37
Problema Matrix Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int M, N, ans;
int a[26][1001][1001];
int t[26];

int main()
{
    fin >> M >> N;

    char c;
    for(int i = 1; i <= M; i++)
        for(int j = 1; j <= M; j++)
        {
            fin >> c;
            a[c - 'a'][i][j]++;
        }

    for(int sigma = 0; sigma <= 'z' - 'a'; sigma++)
        for(int i = 1; i <= M; i++)
            for(int j = 1; j <= M; j++)
                a[sigma][i][j] = a[sigma][i][j] + a[sigma][i - 1][j] + a[sigma][i][j - 1] - a[sigma][i - 1][j - 1];

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
        {
            fin >> c;
            t[c - 'a']++;
        }

    for(int i = N; i <= M; i++)
        for(int j = N; j <= M; j++)
        {
            bool ok = true;

            for(int sigma = 0; sigma <= 'z' - 'a'; sigma++)
                if(a[sigma][i][j] - a[sigma][i - N][j] - a[sigma][i][j - N] + a[sigma][i - N][j - N] != t[sigma])
                {
                    ok = false;
                    break;
                }

            if(ok == true)
                ans++;
        }

    fout << ans;

    return 0;
}