Cod sursa(job #998139)

Utilizator poptibiPop Tiberiu poptibi Data 15 septembrie 2013 21:52:28
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int NMAX = 1010;

int M, N, Freq[NMAX][NMAX], FreqV[30], Ans, Out[NMAX][NMAX];
char S[NMAX], Mat[NMAX][NMAX];

int main()
{
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);

    scanf("%i %i\n", &M, &N);
    for(int i = 1; i <= M; ++ i)
        gets(Mat[i] + 1);


    for(int i = 1; i <= N; ++ i)
    {
        gets(S + 1);
        for(int j = 1; j <= N; ++ j)
            FreqV[ S[j] - 'a' ] ++;
    }

    for(int k = 0; k < 26; ++ k)
    {
        for(int i = 1; i <= M; ++ i)
            for(int j = 1; j <= M; ++ j)
                Freq[i][j] = (Mat[i][j] == 'a' + k) + Freq[i - 1][j] + Freq[i][j - 1] - Freq[i - 1][j - 1];
        for(int i = N; i <= M; ++ i)
            for(int j = N; j <= M; ++ j)
                if(FreqV[k] != Freq[i][j] - Freq[i - N][j] - Freq[i][j - N] + Freq[i - N][j - N])
                    Out[i][j] = 1;
    }

    for(int i = N; i <= M; ++ i)
        for(int j = N; j <= M; ++ j)
            Ans += !Out[i][j];

    printf("%i\n", Ans);

    return 0;
}