Cod sursa(job #1059894)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 17 decembrie 2013 10:32:08
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <cstring>
#include <list>

using namespace std;

#define mod 66013

list<long long int> h[mod];

list<long long int>::iterator gaseste(long long int x)
{
    int b=x%mod;
    list<long long int>::iterator it;
    for(it=h[b].begin();it!=h[b].end();it++)
        if(*it==x)
            break;
    return it;
}

bool exista(long long int x)
{
    int b=x%mod;
    list<long long int>::iterator it=gaseste(x);
    if(it==h[b].end())
        return 0;
    return 1;
}

inline void adauga(long long int x)
{
    int b=x%mod;
    list<long long int>::iterator it=gaseste(x);
    if(it==h[b].end())
        h[b].push_back(x);
}

    char sir[10000005];
    char curent[25];
    int s[10000005],lung;
    int c[25];

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

    cin.get(sir,10000005);

    lung=strlen(sir);

    int i,j,mic;
    for(i=0;i<lung;i++)
        if(sir[i]=='a')
            s[i]=0;
        else if(sir[i]=='b')
            s[i]=1;
        else
            s[i]=2;
    int n;
    //cin>>n;

    long long int val;

    while(1)
    {
        cin.get();
        cin.get(curent,25);
        if(cin.eof())
            break;
        mic=strlen(curent);

        for(j=0;j<mic;j++)
            if(curent[j]=='a')
                c[j]=0;
            else if(curent[j]=='b')
                c[j]=1;
            else
                c[j]=2;
        val=0;
        for(j=0;j<mic;j++)
            val*=3,val+=(c[j]);
        adauga(val);
        //cout<<"adaugam "<<val<<endl;
    }

    int rasp=0;
    long long int put=1;
    val=0;
    for(i=0;i<lung;i++)
    {
        if(i<(mic-1))
            put*=3;
        if(i>=(mic-1))
            val-=((s[i-mic])*put);
        val*=3;
        val+=s[i];
        if(i>=(mic-1))
        {
        //    cout<<"avem la poz "<<i<<endl;
          //  cout<<"val="<<val<<endl;
            if(exista(val))
                rasp++;
        }
    }
    //cout<<"put="<<put<<endl;
    cout<<rasp<<'\n';

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