Cod sursa(job #2474158)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 14 octombrie 2019 19:38:52
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

#define llg     unsigned int

#pragma GCC     optimize("O3")
#define MOD     133337

template <llg P> class HashTable {
public:
    HashTable() {}
    void insert(llg value) {
        if (value < 0) value = value%MOD + MOD;
        llg list = value%P;
        value /= P;
        for (auto &it:hash[list])
            if (it == value) return;
        hash[list].push_back(value);
    }
    bool contains(llg value) {
        if (value < 0) value = value%MOD + MOD;
        llg list = value%P;
        value /= P;
        for (auto &it:hash[list])
            if (it == value) return true;
        return false;
    }
private:
    std::list <llg> hash[P + 1000];
};  HashTable <MOD> Hash;

llg len;
std::string str;

std::ifstream   input ("abc2.in");
std::ofstream   output("abc2.out");

int main()
{
    input >> str;
    std::string word;
    while (input >> word) {
        len = word.size();
        llg hash = 0;
        for (llg i=0; i<word.size(); ++i)
            hash = hash*3 + word[i]-'a';
        Hash.insert(hash);
    }

    llg p = 1, ans = 0;
    for (llg i=0; i<len; ++i)
        p *= 3;
    llg hash = 0;
    for (int i=0; i<len; ++i)
        hash = hash*3 + str[i]-'a';
    ans += Hash.contains(hash);
    for (llg i=len; i<str.size(); ++i) {
        hash = hash*3 + str[i]-'a';
        hash = hash - p*(str[i-len]-'a');
        ans += Hash.contains(hash);
    }   output << ans << '\n';

    return 0;
}