Cod sursa(job #1930228)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 18 martie 2017 17:13:14
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

#define Nmax 1002

using namespace std;

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

int N, M;
int i, j;
char A[Nmax][Nmax], B[Nmax][Nmax];
int S[Nmax][Nmax];
bool OK[Nmax][Nmax];
int F[27];
char ch;
int cnt;

int main()
{
    fin >> N >> M;
    for(i = 1; i <= N; i++)
        fin >> (A[i] + 1);
    for(i = 1; i <= M; i++)
        fin >> (B[i] + 1);
    for(i = 1; i <= M; i++)
        for(j = 1; j <= M; j++)
            F[B[i][j] - 'a']++;
    for(i = M; i <= N; i++)
        for(j = M; j <= N; j++)
            OK[i][j] = true;
    for(ch = 'a'; ch <= 'z'; ch++)
    {
        memset(S, 0, sizeof(S));
        for(i = 1; i <= N; i++)
            for(j = 1; j <= N; j++)
            {
                S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + (A[i][j] == ch);
                if(i >= M && j >= M)
                {
                    if(S[i][j] - S[i - M][j] - S[i][j - M] + S[i - M][j - M] != F[ch - 'a'])
                        OK[i][j] = false;
                }
            }

    }
    for(i = 1; i <= N; i++)
        for(j = 1; j <= N; j++)
            cnt += OK[i][j];
    fout << cnt << "\n";
    return 0;
}