Cod sursa(job #2432780)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 25 iunie 2019 00:24:19
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

const int BASE = 3;
unsigned int getHashCode(string str) {
    unsigned int h = 0;
    for (int i = 0; i < (int) str.size(); i++)
        h = h * BASE + (str[i] - 'a');
    return h;
}

class HashTable {
  private:
    static const int MOD = 8191;
    vector<unsigned int> table[MOD];

  public:
    void insert(unsigned int val) {
        int hash = val % MOD;
        for (unsigned int i : table[hash])
            if (i == val)
                return;
        table[hash].push_back(val);
    }

    bool find(unsigned int val) {
        int hash = val % MOD;
        for (unsigned int i : hash[table])
            if (i == val)
                return true;
        return false;
    }
};

int main() {
    string str; fin >> str;
    HashTable patterns; int len = 0;

    string pattern;
    while (fin >> pattern) {
        len = pattern.size();
        patterns.insert(getHashCode(pattern));
    }

    unsigned int h = getHashCode(str.substr(0, len));
    int sol = patterns.find(h);

    unsigned int pwr = 1;
    for (int i = 1; i < len; i++)
        pwr *= BASE;

    for (int i = len; i < (int) str.size(); i++) {
        h = (h - (str[i - len] - 'a') * pwr) * BASE + (str[i] - 'a');
        sol += patterns.find(h);
    }
    fout << sol << '\n';

    fout.close();
    return 0;
}