Cod sursa(job #1292411)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 14 decembrie 2014 12:16:27
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>

#define NMAX 1007

using namespace std;

int n, m;
int ap[NMAX], Dp[NMAX][NMAX];
char a[NMAX][NMAX],s[NMAX];
bool Ap[NMAX][NMAX];
int Ans;

int main(){
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    for(int i = 1; i <= n; ++i, scanf("\n"))
        gets(a[i] + 1);
    for(int i = 1; i <= m; ++i){
        gets(s + 1);
        for(int j = 1; j <= m; ++j)
            ++ap[s[j] - 'a'];
    }
    for(int c = 0; c < 26; ++c){
        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];
                if(a[i][j]-'a'==c)
                    ++Dp[i][j];
                if(i>=m && j>=m && !Ap[i][j])
                    Ap[i][j] = (Dp[i][j] - Dp[i - m][j] - Dp[i][j - m] + Dp[i - m][j - m] != ap[c]);
            }
        }
    }
    for(int i = m; i <= n; ++i)
        for(int j = m; j <= n; ++j)
            if(!Ap[i][j])
                ++Ans;
    printf("%d", Ans);
    return 0;
}