Cod sursa(job #1830434)

Utilizator maria15Maria Dinca maria15 Data 16 decembrie 2016 18:37:52
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#define dim 1001
#define f first
#define s second

using namespace std;

char v[1002][1002], c, ok[1002][1002];
int f[130];
int i, j, m, n, s[1002][1002];

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

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>>c;
            f[c]++;
        }

    for (int i=m;i<=n;i++)
        for(int j=m;j<=n;j++)
            ok[i][j]=1;

    for (c = 'a'; c <= 'z'; c++) {
        // verificam acum daca in fiecare submatrice litera c apare de acelasi numar de ori ca on vectorul de frecventa
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                s[i][j] = s[i-1][j] + s[i][j-1]-s[i-1][j-1] + (v[i][j] == c);
        // s[i][j] = de cate ori apare litera c in v in submatricea (1,1  i,j)
        for (i=m;i<=n;i++)
            for (j=m;j<=n;j++)
                if (f[c] !=  s[i][j] - s[i-m][j] - s[i][j-m] + s[i-m][j-m])
                    ok[i][j] = 0;
    }
    int nr=0;
    for(i=m;i<=n;i++)
        for(j=m;j<=n;j++)
            if(ok[i][j]==1)
                nr++;
    fout<<nr;

    return 0;
}