Cod sursa(job #3264336)

Utilizator Victor5539Tanase Victor Victor5539 Data 20 decembrie 2024 15:15:03
Problema Matrix Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int ALPHABET=26;
int n,m,i,j,fr[ALPHABET+5],sp[1005][1005][ALPHABET+5],k,fr2[ALPHABET+5],sol;
char v[1005][1005],a;

int nr(char a)
{
    return a-'a'+1;
}

bool verif()
{
    for (int i=1; i<=ALPHABET; i++)
        if (fr[i]!=fr2[i])
            return false;

    return true;
}

void frecventa(int x1,int y1,int x2, int y2)
{
    for (int i=1; i<=ALPHABET; i++)
        fr2[i]=sp[x2][y2][i]-sp[x1-1][y2][i]-sp[x2][y1-1][i]+sp[x1-1][y1-1][i];
}


int main()
{
    fin>>n>>m;

    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            fin>>v[i][j];

    for (i=1; i<=m; i++)
        for (j=1; j<=m; j++)
        {
            fin>>a;
            fr[nr(a)]++;
        }


    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            for (k=1; k<=ALPHABET; k++)
            {
                sp[i][j][k]=sp[i-1][j][k]+sp[i][j-1][k]-sp[i-1][j-1][k];

                if (nr(v[i][j])==k)
                    sp[i][j][k]++;
            }


    for (i=1; i<=n-m+1; i++)
    {
        for (j=1; j<=n-m+1; j++)
        {
            frecventa(i,j,i+m-1,j+m-1);
            if (verif())
                sol++;
        }
    }

    fout<<sol;
    return 0;
}