Cod sursa(job #1849693)

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


const uint64_t hash_mod = 786433;
std::vector<uint64_t> hash[hash_mod];
std::string to_decode, c_word;


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())
        {
                std::getline(fin, c_word);
                if (fin.eof()) break;
                uint64_t hash_key = 0;
                word_size = c_word.size();
                for (uint64_t it = 0; it < word_size; ++it)
                        hash_key = 3* hash_key + c_word[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  = current_key * 3 + to_decode[it] - 'a';
        for (std::vector<uint64_t>::iterator it = hash[current_key % hash_mod].begin(); it != hash[current_key % hash_mod].end(); ++it)
                if (*it == current_key) { ++solution; break; }
        for (uint64_t it = word_size; it < to_decode.size(); ++it)
        {
                current_key = (current_key - power * (to_decode[it - word_size] - 'a')) * 3  + to_decode[it] - 'a';
                for (std::vector<uint64_t>::iterator it2 = hash[current_key % hash_mod].begin(); it2 != hash[current_key % hash_mod].end(); ++it2)
                if (*it2 == current_key)
                {
                        ++solution;
                        break;
                }
        } 

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


}