Cod sursa(job #2108180)

Utilizator dariusdariusMarian Darius dariusdarius Data 17 ianuarie 2018 23:14:21
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <cstring>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>


typedef std::uint32_t uint32;

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

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

    bool find(const uint32 &key, const bool &add, const bool &erase) {
        const uint32 hashedKey = this->hashFunc(key);
        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(const uint32 mod=666013) {
        this->mod = mod;
        this->table.assign(this->mod, 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);
    }
};

std::string str;
char buffer[10000001];

int main() {
//    std::ifstream cin("abc2.in");
    freopen("abc2.in", "r", stdin);
    std::ofstream cout("abc2.out");

    HashTable hashTable;

    fgets(buffer, 10000001, stdin);
    str = buffer;

    char word[22];
    while (fgets(word, 22, stdin)) {
        uint32 hashCode = 0;
        for (int i = 0; word[i] && word[i] != '\n'; ++ i) {
            hashCode = hashCode * 3 + word[i] - 'a';
        }
        hashTable.add(hashCode);
    }

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

    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;
}