Cod sursa(job #2004085)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 24 iulie 2017 21:43:59
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
const int nmax=1004,cmax=30;
int n,m;
char ch[nmax][nmax],ver[nmax][nmax],virus[nmax];
int ap[cmax];
int st[nmax][nmax];
inline void citire()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch[i]+1);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%s",virus);
        for(int j=0;j<n;j++) ap[virus[j]-'a']++;
    }
}
void build_st(int vir)
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(ch[i][j]-'a'==vir) st[i][j]=1;
            else st[i][j]=0;
            st[i][j]+=st[i-1][j]+st[i][j-1]-st[i-1][j-1];
        }
    }
}
inline void verificare(int vir)
{
    for(int i=n;i<=m;i++)
    {
        for(int j=n;j<=m;j++)
        {
            int p1=i-n+1,p2=j-n+1;
            int sum=st[i][j]-st[i][p2-1]-st[p1-1][j]+st[p1-1][p2-1];
            if(sum!=ap[vir]) ver[i][j]=1;
        }
    }
}
inline void solve()
{
    for(int vir=0;vir<26;vir++)
    {
        build_st(vir);
    }
    int ct=0;
    for(int i=n;i<=m;i++)
    {
        for(int j=n;j<=m;j++) if(ver[i][j]==0) ++ct;
    }
    printf("%d\n",ct);
}
int main()
{
    freopen ("matrix.in","r",stdin);
    freopen ("matrix.out","w",stdout);
    citire();
    solve();
}