Pagini recente » Cod sursa (job #1513495) | Statistici Tothazan Dragos (Cr7_UistU) | Cod sursa (job #1628995) | Cod sursa (job #435941) | Cod sursa (job #1539172)
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
template <int dim, uint32_t mult, uint32_t xord, uint32_t inf>
class my_hash{
array<uint32_t, dim> buf;
uint32_t hash(const uint32_t x){
return ((x*mult) ^ xord)%dim; }
public:
my_hash(){
for(auto& x : buf){
x = inf; } }
bool find(uint32_t x){
uint32_t i = hash(x), i0 = i;
for( ; ; ){
if(buf[i] == inf){
return false; }
if(buf[i] == x){
return true; }
++i;
if(i == dim){
i = 0; }
if(i == i0){
return false; } } }
void insert(uint32_t x){
uint32_t i = hash(x);
for( ; ; ){
if(buf[i] == inf){
buf[i] = x;
return; }
++i;
if(i == dim){
i = 0; } } } };
int main(){
ifstream f("abc2.in");
ofstream g("abc2.out");
string str;
str.reserve(10000000);
f >> str;
my_hash<2000000, 17, 5, 3486784401> words;
int len = 0;
{
string word;
while(f >> word){
uint32_t cod = 0;
for(const auto x : word){
cod = cod * 3 + x - 'a'; }
words.insert(cod); }
len = word.size(); }
uint32_t pow_of_3 = 1;
for(int i = 0; i < len-1; ++i){
pow_of_3 *= 3; }
uint32_t cod = 0;
for(int i = 0; i < len; ++i){
cod = cod * 3 + str[i] - 'a'; }
int rez = words.find(cod);
for(int st = 0, dr = len; dr < str.size(); ++st, ++dr){
cod -= pow_of_3 * (str[st]-'a');
cod = 3 * cod + str[dr] - 'a';
rez += words.find(cod); }
g << rez;
return 0; }