Cod sursa(job #2108170)

Utilizator dariusdariusMarian Darius dariusdarius Data 17 ianuarie 2018 23:01:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>


class HashTable {
private:
    std::vector<std::vector<size_t>> table;
    size_t mod = 666013;

    inline size_t hashFunc(const size_t &key) {
        return key % this->mod;
    }

    bool find(const size_t &key, const bool &add, const bool &erase) {
        const size_t hashedKey = this->hashFunc(key);
        for (size_t &value: this->table[hashedKey]) {
            if (value == key) {
                if (erase) {
                    value = this->table[hashedKey].back();
                    this->table[hashedKey].pop_back();
                    return false;
                }
                return true;
            }
        }
        if (add) {
            this->table[hashedKey].push_back(key);
            return true;
        }
        return false;
    }
public:
    HashTable(const size_t mod=666013) {
        this->mod = mod;
        this->table.assign(this->mod, std::vector<size_t>());
    }

    bool has(const size_t &key) {
        return this->find(key, false, false);
    }

    bool add(const size_t &key) {
        return this->find(key, true, false);
    }

    bool erase(const size_t &key) {
        return this->find(key, false, true);
    }
};

int main() {
    std::ifstream cin("abc2.in");
    std::ofstream cout("abc2.out");

    std::string str;
    std::string word;

    HashTable hashTable;

    cin >> str;
    while (cin >> word) {
        size_t hashCode = 0;
        for (const char &ch: word) {
            hashCode = hashCode * 3 + ch - 'a';
        }
        hashTable.add(hashCode);
    }

    if (str.length() < word.length()) {
        cout << 0 << std::endl;
        return 0;
    }

    // 3 ^ (word.length() - 1)
    size_t power = 1;
    for (int i = 1; i < word.length(); ++ i) {
        power *= 3;
    }

    size_t rollingHash = 0;
    for (int i = 0; i < word.length(); ++ i) {
        rollingHash = rollingHash * 3 + str[i] - 'a';
    }

    size_t result = 0;
    if (hashTable.has(rollingHash)) {
        result += 1;
    }
    for (int i = word.length(); i < str.length(); ++ i) {
        rollingHash -= power * (str[i - word.length()] - 'a');
        rollingHash = rollingHash * 3 + str[i] - 'a';
        if (hashTable.has(rollingHash)) {
            result += 1;
        }
    }
    cout << result << std::endl;
    return 0;
}