Cod sursa(job #1061444)

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

const int MAX_N = 1002;
const int SIGMA = 26;
int N, M, sol;
int freq[SIGMA];
short int dp[MAX_N][MAX_N][SIGMA];
char s[MAX_N], A[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 = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            for(int k = 0; k < SIGMA; ++k)
                dp[i][j][k] = dp[i - 1][j][k] + dp[i][j - 1][k] - dp[i - 1][j - 1][k] + ((A[i][j] - 'a') == k);
    for(int i = M; i <= N; ++i)
        for(int j = M; j <= N; ++j) {
            bool ok = 1;
            for(int k = 0; k < SIGMA; ++k)
                if(freq[k] != dp[i][j][k] - dp[i - M][j][k] - dp[i][j - M][k] + dp[i - M][j - M][k])
                    ok = 0, k = SIGMA;
            sol += ok;
        }

    g << sol << "\n";

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

    return 0;
}