Cod sursa(job #3255346)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 10 noiembrie 2024 13:46:47
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int nmax = 1000;


int n,m;

char txt[nmax+5][nmax+5];

int pat[nmax +5][nmax + 5];

int f[30];

int sol;


int d[nmax + 5][nmax + 5];

bool ok[nmax + 5][nmax + 5];


int main()
{
    fin>>m>>n;
    for(int i=1;i<=m;i++)
        fin>>txt[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            char x;
            fin>>x;
            f[x-'a']++;
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++){
            ok[i][j]=true;
            if(i<n || j < n)
                ok[i][j]=false;
        }


    for(int ch = 'a';ch<='z';ch++)
    {


        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
                d[i][j] = d[i-1][j] + d[i][j-1] - d[i-1][j-1] + (txt[i][j-1]==ch);
        for(int i = m ; i>=n;i--)
            for(int j = m;j>=n;j--)
                if(d[i][j]+d[i-n][j-n]-d[i-n][j]-d[i][j-n]!=f[ch-'a'])
                    ok[i][j]=false;
        /*
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++)
                fout<<d[i][j]<<' ';
            fout<<'\n';
        }
        fout<<'\n';
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++)
                fout<<ok[i][j]<<' ';
            fout<<'\n';
        }*/

    }

    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            sol+=ok[i][j];
    fout<<sol;
}