Cod sursa(job #1539172)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 30 noiembrie 2015 13:36:19
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#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; }