Cod sursa(job #1059898)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 17 decembrie 2013 10:36:09
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

#define mod 99991

vector<unsigned int> h[mod];

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

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

inline void adauga(unsigned int x)
{
    int b=x%mod;
    vector<unsigned 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;

    unsigned 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;
    unsigned 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;
}