Cod sursa(job #1700219)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 9 mai 2016 20:38:55
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 1000 + 2;
constexpr int SIGMA = 26;

int sum[MAX_N][MAX_N];
int ok[MAX_N][MAX_N];
int cnt[SIGMA];
char A[MAX_N][MAX_N];
char B[MAX_N][MAX_N];
int N, M;

int main()
{
    ifstream in("matrix.in");
    ofstream out("matrix.out");

    in >> N >> M;

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

    for (int i = 1; i <= M; ++i)
    {
        in >> (B[i] + 1);

        for (int j = 1; j <= M; ++j)
            cnt[ B[i][j] - 'a' ]++;
    }

    for (int c = 0; c < SIGMA; ++c)
    {
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (A[i][j] - 'a' == c);

        for (int i = 1; i + M - 1 <= N; ++i)
            for (int j = 1; j + M - 1 <= N; ++j)
            {
                int a = i + M - 1;
                int b = j + M - 1;

                int S = sum[a][b] - sum[i - 1][b] - sum[a][j - 1] + sum[i - 1][j - 1];

                ok[i][j] += (S == cnt[c]);
            }
    }

    int sol = 0;

    for (int i = 1; i + M - 1 <= N; ++i)
        for (int j = 1; j + M - 1 <= N; ++j)
            sol += (ok[i][j] == SIGMA);

    out << sol << endl;

    return 0;
}