Cod sursa(job #1700855)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 11 mai 2016 15:35:09
Problema Matrix Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>

#define NMax 1002
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");

int n,m,ANS;
char x[NMax];
char v[NMax];
char A[NMax][NMax];
char M[29][NMax][NMax];

int main()
{
    f >> n >> m;
  //  g << 1.0*(sizeof(A)*26)/1024/1024;
    f.get();
    for(int i = 1; i <= n; ++i){
        f.getline(x,NMax);
        for(int j = 0; j < n; ++j){
            A[i][j + 1] = x[j] - 'a';
        }
    }
    for(int i = 1; i <= m; ++i){
        f.getline(x,NMax);
        for(int j = 0; j < m; ++j){
            v[x[j] - 'a']++;
        }
    }
    for(int lit = 0; lit <= 'z' - 'a'; ++lit){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                M[lit][i][j] = M[lit][i - 1][j] + M[lit][i][j - 1] - M[lit][i - 1][j - 1];
                if(A[i][j] == lit){
                    M[lit][i][j] ++;
                }
            }
        }
    }
    for(int i = m; i <= n; ++i){
        for(int j = m; j <= n; ++j){

            int ok = 1;
            for(int lit = 0; lit <= 'z' - 'a'; ++lit){
                int Nr = M[lit][i][j] - M[lit][i - m][j] - M[lit][i][j - m] + M[lit][i - m][j - m];
                if(v[lit] != Nr){
                    ok = 0;
                    break;
                }
            }
            if(ok == 1){
                ANS++;
            }
        }
    }
    g << ANS << '\n';
    return 0;
}