Cod sursa(job #2272750)

Utilizator giotoPopescu Ioan gioto Data 30 octombrie 2018 17:08:08
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
char s[1005];
int f[26];
int d[1005][1005];
char a[1005][1005];
bool ok[1005][1005];
int main(){
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n ; ++i){
        scanf("%s", a[i] + 1);
        for(int j = 1; j <= n ; ++j)
            ok[i][j] = 1;
    }

    for(int j = 1; j <= m ; ++j){
        scanf("%s", s + 1);
        for(int j = 1; j <= m ; ++j)
            ++f[s[j] - 'a'];
    }

    for(int c = 0; c < 26 ; ++c){
        for(int i = 1; i <= n ; ++i)
            for(int j = 1; j <= n ; ++j)
                d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + ((a[i][j] - 'a') == c);

        int Sol = 0;
        for(int i = m; i <= n ; ++i){
            for(int j = m; j <= n ; ++j){
                if(!ok[i][j]) continue ;
                int ap = d[i][j] - d[i - m][j] - d[i][j - m] + d[i - m][j - m];
                if(ap != f[c]) ok[i][j] = 0;
            }
        }
    }

    int Sol = 0;
    for(int i = m; i <= n ; ++i)
        for(int j = m; j <= n ; ++j)
            Sol += ok[i][j];
    printf("%d", Sol);

    return 0;
}