Cod sursa(job #1334453)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 4 februarie 2015 13:35:17
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#define DIM 1001
using namespace std;

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

int  N, M, i, j, k, ok, minim;
char A[DIM][DIM], B[DIM][DIM];
int  v[30], C[DIM][DIM];
int  D[DIM][DIM], nr;

void SetUp(){
    fin >> N >> M; nr = 0;
    for(i = 1; i <= N + 10; i ++)
        for(j = 1; j <= N + 10; j ++)
            D[i][j] = 1;

    for(i = 1; i <= N; i ++)
        fin >> A[i] + 1;

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

    for(k = 0; k < 26; k ++){

        for(i = 1; i <= N; i ++)
            for(j = 1; j <= N; j ++){
                C[i][j] = C[i-1][j] + C[i][j-1] - C[i-1][j-1];
                if(A[i][j] - 'a' == k)
                    C[i][j] ++;
            }

        for(i = M; i <= N; i ++)
            for(j = M; j <= N; j ++)
                if(D[i][j] == 1 && C[i][j] - C[i-M][j] - C[i][j-M] + C[i-M][j-M] == v[k]){
                    if(k == 25)
                        nr ++;
                }
                else
                    D[i][j] = 0;

    }
    fout << nr;
    return;
}

int main(){
    SetUp();
    return 0;
}