Cod sursa(job #1163824)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 1 aprilie 2014 17:19:40
Problema Matrix Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <cstring>

using namespace std;

struct elem
{
    int frecv[26];

    /*
    inline elem()
    {
        int i;
        for(i=0;i<26;i++)
            frecv[i]=0;
    }*/

    inline void operator=(const elem a)
    {
        int i;
        for(i=0;i<26;i++)
            frecv[i]=a.frecv[i];
    }

    inline bool operator==(const elem a)
    {
        int i;

        bool ok=true;
        for(i=24;i>=0;i--)
            if(frecv[i]!=a.frecv[i])
            {
                ok=false;
                break;
            }
        return ok;
    }

    /*
    inline void add(char x)
    {
        frecv[x-'a']++;
    }

    inline void subtract(char x)
    {
        frecv[x-'a']--;
    }*/

    /*void afis()
    {
        int i;
        cout<<endl;
        for(i=0;i<26;i++)
            cout<<frecv[i]<<' ';
        cout<<endl;
    }*/
};

char mat[1005][1005];
char nou[1005][1005];
elem v[1005];
elem model;

int main()
{
    ifstream cin("matrix.in");
    ofstream cout("matrix.out");

    int n=0,m=0,i,j;

    cin>>n>>m;
    for(i=0;i<n;i++)
    {
        cin.get();
        cin.get(mat[i],1005);
    }

    for(i=0;i<m;i++)
    {
        cin.get();
        cin.get(nou[i],1005);

        for(j=0;j<m;j++)
            model.frecv[nou[i][j]-'a']++;
    }

    for(i=0;i<m;i++)
        for(j=0;j<m;j++)
            v[0].frecv[mat[i][j]-'a']++;

    int cate=0,k;
    cate+=(v[0]==model);

    elem curent;
    curent=v[0];

    for(j=1;j+m-1<n;j++)
    {
        for(k=0;k<=(m-1);k++)
        {
            curent.frecv[mat[k][j-1]-'a']--;
            curent.frecv[mat[k][j+m-1]-'a']++;
        }

        cate+=(curent==model);
    }

    for(i=1;i+m-1<n;i++)
    {
        v[i]=v[i-1];

        for(j=0;j<m;j++)
        {
            v[i].frecv[mat[i-1][j]-'a']--;
            v[i].frecv[mat[i+m-1][j]-'a']++;
        }

        cate+=(v[i]==model);

        elem curent;
        curent=v[i];

        for(j=1;j+m-1<n;j++)
        {
            for(k=i;k<=(i+m-1);k++)
            {
                curent.frecv[mat[k][j-1]-'a']--;
                curent.frecv[mat[k][j+m-1]-'a']++;
            }

            cate+=(curent==model);
        }
    }

    cout<<cate<<'\n';

    cin.close();
    cout.close();
    return 0;
}