Cod sursa(job #1850639)

Utilizator teo.cons98Constantin Teodor-Claudiu teo.cons98 Data 18 ianuarie 2017 20:09:35
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");

struct
{
    int nr = 0;
    vector<string> str;
}v[666013];

string s,s1,s2;
char c;
long long dim, strln, putere, nr1, contor = 0;
void adaugareHash()
{
    unsigned long long nr1 = 0,strln, putere = 1,e = 0;
    for(int i = 0; i < s1.size(); ++i)
    {
        putere %= 666013;
        if(s1[i] == 'b')
        {
            nr1 += putere;
        }
        if(s1[i] == 'c')
        {
            nr1 += putere * 2;
        }
        nr1 %= 666013;
        putere *= 3;
    }
    //cout<<nr1<<endl;
    if(v[nr1].nr == 0)
    {
        ++v[nr1].nr;
        v[nr1].str.push_back(s1);
        //cout<<s1<<endl;
    }
    else
    {
        for(int i = 0; i < v[nr1].nr; ++i)
        {
            if(v[nr1].str[i] == s1)
            {
                e = 1;
                break;
            }
        }
        if(e == 0)
        {
            ++v[nr1].nr;
            v[nr1].str.push_back(s1);
            //cout<<s1<<endl;
        }
    }
}

void citire()
{
    int a = 0;
    fin>>s;
    strln = s.size();
    while(fin>>s1)
    {
        adaugareHash();
    }
    dim = s1.size();
}


void verificare(int x)
{
    int e = 0, k = dim - 1;
    for(int i = 0; i < v[nr1].nr; ++i)
    {
        e = 0;
        k = dim - 1;
        for(int j = x + dim - 1; j >= x; --j)
        {
            if(v[nr1].str[i][k] != s[j])
            {
                e = 1;
                break;
            }
                --k;
        }
        if(e == 0)
        {
            ++contor;
            break;
        }
    }
}
int main()
{
    citire();
    //cout<<dim<<endl;
    putere = 1;
    nr1 = 0;
    for(int i = strln - 1; i > strln - dim - 1; --i)
    {
        nr1 *= 3;
        putere %= 666013;
        if(s[i] == 'b')
        {
            nr1 += 1;
        }
        if(s[i] == 'c')
        {
            nr1 += 2;
        }
        putere *= 3;
        nr1 %= 666013;
    }
    //cout<<nr1;
    if(v[nr1].nr > 0)
    {
        //cout<<"1";
        ++contor;
    }
    putere = powl(3, dim);
    //cout<<putere<<endl;
    putere %= 666013;
    for(int i = strln - dim - 1; i >= 0; --i)
    {
        //cout<<nr1<<endl;
        //cout<<"haha"<<endl;
        nr1 *= 3;
        if(s[i + dim] == 'b')
        {
            nr1 -= putere;

        }
        if(s[i + dim] == 'c')
        {
            nr1 -= (putere * 2);
        }
        /*if(nr1 < 0)
        {
            nr1 = 666013 + nr1;
        }*/
        if(s[i] == 'b')
        {
            nr1 += 1;
        }
        if(s[i] == 'c')
        {
            nr1 += 2;
        }
        nr1 %= 666013;
        if(v[nr1].nr > 0)
        {
            ++contor;
        }
    }
    fout<<contor;
}