Cod sursa(job #2474147)

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

#define llg     unsigned int

#define MOD     5099

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

int 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 (int i=0; i<(int) word.size(); ++i)
            hash = hash*3 + word[i]-'a';
        Hash.insert(hash);
    }

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

    return 0;
}