Cod sursa(job #2004068)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 24 iulie 2017 20:28:04
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>

const int MAXN = (int) 1e3 + 1;
const int SIGMA = 26;

char a[MAXN + 1][MAXN + 1];
char b[MAXN + 1][MAXN + 1];
int fr[SIGMA];

int cnt[MAXN + 1][MAXN + 1];
int sp[MAXN + 1][MAXN + 1];

int main() {
    FILE *fi, *fout;
    int i, j, n, m;
    fi = fopen("matrix.in" ,"r");
    fout = fopen("matrix.out" ,"w");
    fscanf(fi,"%d %d " ,&n,&m);
    for(i = 1; i <= n; i++)
        fscanf(fi,"%s " ,a[i] + 1);
    int x = 0;
    for(i = 1; i <= m; i++) {
        fscanf(fi,"%s " ,b[i] + 1);
        for(j = 1; j <= m; j++) {
            if(fr[b[i][j] - 'a'] == 0)
               x++;
            fr[b[i][j] - 'a']++;
        }
    }
    for(char ch = 'a'; ch <= 'z'; ch++)
        if(fr[ch - 'a'] > 0) {
            memset(sp, 0,sizeof(sp));
            for(i = 1; i <= n; i++)
              for(j = 1; j <= n; j++) {
                  if(a[i][j] == ch)
                     sp[i][j] = 1;
                  sp[i][j] += sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];
              }
            for(i = m; i <= n; i++)
              for(j = m; j <= n; j++)
                  if(sp[i][j] - sp[i - m][j] - sp[i][j - m] + sp[i - m][j - m] == fr[ch - 'a'])
                     cnt[i][j]++;
        }
    int ans = 0;
    for(i = m; i <= n; i++)
        for(j = m; j <= n; j++)
          if(cnt[i][j] == x)
              ans++;
    fprintf(fout,"%d" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}