Cod sursa(job #2205383)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 18 mai 2018 22:40:05
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>

using namespace std;
char a[1002][1002];
int f[26],aux[26];
int d[1002][1002][26];
int main()
{
    int n,m,i,j,k,nr;
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    getchar();
    for(i=1; i<=n; i++)
        for(j=1; j<=n+1; j++)
            a[i][j]=getchar();
    for(i=1; i<=m; i++)
        for(j=1; j<=m+1; j++)
        {
            int c=getchar();
            if(j<m+1)
                f[c-'a']++;
        }
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            for(k=0; k<26; k++)
                d[i][j][k]=d[i][j-1][k];
            d[i][j][a[i][j]-'a']++;
        }
    for(j=1; j<=n; j++)
        for(i=1; i<=n; i++)
        {
            for(k=0; k<26; k++)
                d[i][j][k]+=d[i-1][j][k];
        }
    nr=0;
    for(i=m; i<=n; i++)
        for(j=m; j<=n; j++)
        {
            for(k=0; k<26; k++)
                aux[k]=d[i][j][k]+d[i-m][j-m][k]-d[i-m][j][k]-d[i][j-m][k];
            for(k=0; k<26; k++)
                if(aux[k]!=f[k])
                    break;
            if(k==26)
                nr++;
        }
    printf("%d",nr);

    return 0;
}