Cod sursa(job #2108191)

Utilizator dariusdariusMarian Darius dariusdarius Data 17 ianuarie 2018 23:21:43
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>


typedef std::uint32_t uint32;

class HashTable {
private:
    std::vector<std::vector<uint32>> table;

    bool find(const uint32 &key, const bool &add, const bool &erase) {
        const uint32 hashedKey = key & 524287;
        for (uint32 &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() {
        this->table.assign(524288, std::vector<uint32>());
    }

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

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

    bool erase(const uint32 &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) {
        uint32 hashCode = 0;
        for (const char &ch: word) {
            hashCode = hashCode * 3 + ch - 'a';
        }
        hashTable.add(hashCode);
    }

    uint32 strLength = str.length();
    uint32 wordLength = word.length();

    if (strLength < wordLength) {
        cout << 0 << std::endl;
        return 0;
    }

    // 3 ^ (wordLength - 1)
    uint32 power = 1;
    for (int i = 1; i < wordLength; ++ i) {
        power *= 3;
    }

    uint32 rollingHash = 0;
    for (int i = 0; i < wordLength; ++ i) {
        rollingHash = rollingHash * 3 + str[i] - 'a';
    }

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