Pagini recente » Cod sursa (job #1324455) | Cod sursa (job #1849696)
#include <fstream>
#include <stdint.h>
#include <vector>
#include <string>
#include <cmath>
const uint32_t hash_mod = 786433;
std::vector<uint32_t> hash[hash_mod];
std::string to_decode, c_word;
int32_t main()
{
std::ifstream fin("abc2.in");
std::ofstream fout("abc2.out");
uint32_t word_size = 0;
std::getline(fin, to_decode);
while (!fin.eof())
{
std::getline(fin, c_word);
if (fin.eof()) break;
uint32_t hash_key = 0;
word_size = c_word.size();
for (uint32_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);
}
uint32_t power = pow(3, word_size - 1);
uint32_t solution = 0;
uint32_t current_key = 0;
for (uint32_t it = 0; it < word_size; ++it)
current_key = current_key * 3 + to_decode[it] - 'a';
for (std::vector<uint32_t>::iterator it = hash[current_key % hash_mod].begin(); it != hash[current_key % hash_mod].end(); ++it)
if (*it == current_key) { ++solution; break; }
for (uint32_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<uint32_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;
}