Cod sursa(job #1850718)

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

struct
{
    int nr = 0;
    vector<unsigned int> str;
}v[666015];

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)
    { nr1+=putere*(s1[i]-'a');
      putere *= 3;
    }

    if(v[nr1%MOD].nr == 0)
    {
        ++v[nr1%MOD].nr;
        v[nr1%MOD].str.push_back(nr1);
    }
    else
    { e = 0;
        for(int i = 0; i < v[nr1%MOD].nr; ++i)
        {
            if(v[nr1%MOD].str[i] == nr1)
            {
                e = 1;
                break;
            }
        }

        if(e == 0)
        {
            ++v[nr1%MOD].nr;
            v[nr1%MOD].str.push_back(nr1);
            //cout<<s1<<endl;
        }
    }
}

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

    }
    dim = s1.size();
}


void verificare(unsigned int x)
{
    unsigned int e = 0, k = dim - 1;

    for(int i = 0; i < v[nr1%MOD].nr; ++i)
    {

        if (v[nr1%MOD].str[i]==nr1)
        {
            ++contor;
            break;
        }
    }

}

int main()
{ int i;
    citire();
    //cout<<dim<<endl;
    nr1 = 0;

    for(i = strln - 1; i >= strln - dim; --i)
    {
        nr1 *= 3;

        if(s[i] == 'b')
        {
            nr1 += 1;
        }
        if(s[i] == 'c')
        {
            nr1 += 2;
        }


    }

    if(v[nr1%MOD].nr > 0)
    {
        //cout<<"1";
        verificare(strln-dim);
    }

    putere = powl(3, dim);
    //cout<<putere<<endl;

    for(int i = strln - dim - 1; i >= 0; --i)
    {
        nr1 *= 3;

        nr1 -= putere * (s[i + dim]-'a');

        nr1 += s[i]-'a';


        if(v[nr1%MOD].nr > 0)
        {
            verificare(i);
        }
    }
    fout<<contor;

 return 0;
}