Cod sursa(job #1061452)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 19 decembrie 2013 19:55:31
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
using namespace std;

const int MAX_N = 1002;
const int SIGMA = 26;

int N, M, sol;
int freq[SIGMA], dp[MAX_N][MAX_N];
char s[MAX_N], A[MAX_N][MAX_N];
bool OK[MAX_N][MAX_N];

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

    f >> N >> M;
    for(int i = 1; i <= N; ++i)
        f >> (A[i] + 1);
    for(int i = 1; i <= M; ++i) {
        f >> s;
        for(int j = 0; j < M; ++j)
            ++freq[s[j] - 'a'];
    }

    for(int i = M; i <= N; ++i)
        for(int j = M; j <= N; ++j)
            OK[i][j] = 1;

    for(int k = 0; k < SIGMA; ++k) {
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + ((A[i][j] - 'a') == k);
        for(int i = M; i <= N; ++i)
            for(int j = M; j <= N; ++j) {
                if(OK[i][j] == 0)
                    continue;
                if(freq[k] != dp[i][j] - dp[i - M][j] - dp[i][j - M] + dp[i - M][j - M])
                        OK[i][j] = 0;
            }
    }

    for(int i = M; i <= N; ++i)
        for(int j = M; j <= N; ++j)
            sol += OK[i][j];

    g << sol << "\n";

    f.close();
    g.close();

    return 0;
}