Cod sursa(job #935447)

Utilizator rudarelLup Ionut rudarel Data 3 aprilie 2013 14:54:36
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
# include <stdio.h>
# include <string.h>
 
# define  _fin  "matrix.in"
# define  _fout "matrix.out"
 
# define  maxn  1001
# define  sigma 'z'+5
 
 
int n, m, i, j, f[sigma], aux, sol,
    o[maxn][maxn], t[maxn][maxn];
char a[maxn][maxn], b[maxn][maxn], c;
 
 
void readf()
{
    freopen(_fin, "r", stdin);
    for (scanf("%d%d", &n, &m), i=1; i<=n; i++) scanf("%s", a[i]+1);
    for (i=1; i<=m; i++) {
        scanf("%s", b[i]+1);
        for (j=1; j<=m; j++) ++f[b[i][j]];
    }
}
 
void solve()
{
    for (i=1; i<=n; i++) for (j=1; j<=n; j++) o[i][j]=1;
     
    for (c='a'; c<='z'; c++) {
        memset(t, 0, sizeof(t));
        for (i=1; i<=n; i++)
            for (j=1; j<=n; j++)
                t[i][j] = t[i-1][j]+t[i][j-1]-t[i-1][j-1]+(a[i][j]==c);
         
        for (i=m; i<=n; i++)
            for (j=m; j<=n; j++) {
                aux = t[i][j]-t[i-m][j]-t[i][j-m]+t[i-m][j-m];
                o[i][j] &= (aux==f[c]);
            }
    }
     
    for (i=m; i<=n; i++)
        for (j=m; j<=n; j++) sol += o[i][j];
}
 
int main()
{
    readf();
    solve();
     
    fprintf(fopen(_fout,"w"), "%d\n", sol);
     
    return 0;
}