Cod sursa(job #2293364)

Utilizator cameliapatileaPatilea Catalina Camelia cameliapatilea Data 30 noiembrie 2018 22:08:13
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 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<int>hash_table[35678];

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

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

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

    f>>text_makako;
    lungime_sir = strlen(text_makako);
    while (f >> cuvant)
    {
        lungime_cuvant = strlen(cuvant);
        int 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);
    }

    aux = lungime_cuvant;

    while (aux > 1)
    {
        p = p * 3;
        aux--;
    }

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