Pagini recente » Cod sursa (job #2618261) | Cod sursa (job #1033193) | Cod sursa (job #517444) | Cod sursa (job #1113186) | Cod sursa (job #1849681)
#include <fstream>
#include <stdint.h>
#include <vector>
#include <string>
#include <cmath>
const uint64_t hash_mod = 666013;
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;
}