Cod sursa(job #2293393)

Utilizator cameliapatileaPatilea Catalina Camelia cameliapatilea Data 30 noiembrie 2018 22:29:41
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>

using namespace std;
char text_makako[10000005];
ifstream f("abc2.in");
ofstream g("abc2.out");

char cuvant[23];
vector<long long >hash_table[50002];

inline void adauga_in_hash(long long x)
{
    int poz = x % 50002;
    hash_table[poz].push_back(x);
}

int verifica(long long x) {
    int pozitie = x % 50002;
    int ok = 0;
    int dimensiune = hash_table[pozitie].size();
    for(int i = 0; i< dimensiune; i++)
        if(hash_table[pozitie][i] == x) ok = 1;
    return ok;
}

int main() {
    int lungime_sir, lungime_cuvant;
    int solutie = 0;
    long long p = 1;
    int aux;
    long long hash_curent = 0;

    f>>text_makako;
    lungime_sir = strlen(text_makako);
    while (f >> cuvant)
    {
        lungime_cuvant = strlen(cuvant);
        long long k = 0;
        //pentru fiecare cuvant, genereaza un hash
        for (int i = 0; i < lungime_cuvant; i++)
            //codez fiecare cuvant si ii creez in hash o legatura
            k = k * 3 + (cuvant[i] - 'a');
        adauga_in_hash(k);
    }
    
    for(int i = 1; i< lungime_cuvant; i++)
        p = p * 3;

    for(int i = 0; i< lungime_cuvant; i++)
        //fac un caz separat pt primul "cuvant", creez hashul si il caut
        hash_curent = hash_curent * 3 + text_makako[i] - 'a';
    if(verifica(hash_curent) != 0)
        solutie ++;
    //pentru fiecare litera in parte parcurg sirul
   for( int i = lungime_cuvant; i < lungime_sir; i++)
   {
       //si elimin de fiecare data prima litera din fostul cuvant
       hash_curent = hash_curent - (text_makako[i - lungime_cuvant] - 'a') * p;
       //noua litera venita e adaugata in hash(creez un nou cod)
       hash_curent = hash_curent * 3 + text_makako[i] - 'a';
       if(verifica(hash_curent) != 0)
           solutie ++;
   }
   g << solutie;
   return 0;
}