Cod sursa(job #492609)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 15 octombrie 2010 12:11:02
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<cstdio>
const int N=1<<10;
short int f[27],sus[N][N][27],st[N][N][27];
int nr,n,m;
char a[N][N],v[N][N];
void read()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    for(int i=1;i<=n;i++)
        gets(a[i]+1);
    for(int i=1;i<=m;i++)
        gets(v[i]+1);
}
void copy(short int a[27],short int b[27])
{
    for(int i=1;i<=26;i++)
        a[i]=b[i];
}
void copyi(int a[27],int b[27])
{
    for(int i=1;i<=26;i++)
        a[i]=b[i];
}
void init_mat()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            copy(sus[i][j],sus[i-1][j]);
            sus[i][j][a[i][j]-'a'+1]++;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            copy(st[i][j],st[i][j-1]);
            st[i][j][a[i][j]-'a'+1]++;
        }
}
void getf()
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            f[v[i][j]-'a'+1]++;
}
void solve()
{
    int fr[27],afr[27];
    for(int i=0;i<=26;i++)
        fr[i]=afr[i]=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            fr[a[i][j]-'a'+1]++;
    for(int i=m;i<=n;i++)
    {
        copyi(afr,fr);
        for(int j=m;j<=n;j++)
        {
            bool ok=true;
            for(int k=1;k<=26;k++)
                if(fr[k]!=f[k])
                {
                    ok=false;
                    break;
                }
            if(ok)
                nr++;
            for(int k=1;k<=26;k++)
                fr[k]+=(sus[i][j+1][k]-sus[i-m][j+1][k])-(sus[i][j+1-m][k]-sus[i-m][j+1-m][k]);
        }
        copyi(fr,afr);
        for(int k=1;k<=26;k++)
            fr[k]+=st[i+1][m][k]-st[i+1-m][m][k];
    }
}
int main()
{
    read();
    init_mat();
    getf();
    solve();
    printf("%d",nr);
    return 0;
}