Cod sursa(job #1849678)

Utilizator aaether14Dinescu Stefan Cristian aaether14 Data 17 ianuarie 2017 19:21:09
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <stdint.h>
#include <vector>
#include <string>
#include <cmath>


const uint64_t hash_mod = 20011;
std::vector<uint64_t> hash[hash_mod];
std::string to_decode;


int32_t main()
{


        std::ifstream fin("abc2.in");
        std::ofstream fout("abc2.out");
        uint64_t word_size = 0;


        std::getline(fin, to_decode);
        while (!fin.eof())
        {
                uint64_t hash_key = 0;
                std::string c_word;
                std::getline(fin, c_word);
                if (fin.eof()) break;
                word_size = c_word.size();
                for (auto it : c_word)  {hash_key *= 3; hash_key += (it - 'a');}
                hash[hash_key % hash_mod].push_back(hash_key);
        }


        uint64_t power = pow(3, word_size - 1);
        uint64_t solution = 0;
        uint64_t current_key = 0;
        for (uint64_t it = 0; it < word_size; ++it)
        {
                current_key *= 3;
                current_key += (to_decode[it] - 'a');
        }
        for (auto it : hash[current_key % hash_mod]) {if (it == current_key) ++solution; break;}
        for (uint64_t it = word_size; it < to_decode.size(); ++it)
        {
                current_key -= (power * (to_decode[it - word_size] - 'a'));
                current_key *= 3;
                current_key += (to_decode[it] - 'a');
                for (auto it2 : hash[current_key % hash_mod]) {if (it2 == current_key) ++solution; break;}
        } 

        fout << solution;
        fout.close();
        fin.close();
        return 0;


}