Cod sursa(job #2806963)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 23 noiembrie 2021 10:57:42
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <vector>

using namespace std;

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

#pragma GCC optimize("Ofast")

const int base = 3, mod = 1500007;
int ans;
string s, cuv;
vector <unsigned int> dictionar[mod];
int len, s_len;
unsigned int base_pow;

bool check(unsigned int Hash)
{
    unsigned int modh = Hash % mod;
    for(int i = 0; i < (int) dictionar[modh].size(); i++)
        if(Hash == dictionar[modh][i])
            return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fin >> s;
    s_len = s.size();
    while(fin >> cuv)
    {
        len = cuv.size();
        unsigned int myHash = 0;
        for(int i = 0; i < len; i++)
            myHash = myHash * base + (cuv[i] - 'a');
        if(!check(myHash))
        {
            unsigned int modh = myHash % mod;
            dictionar[modh].push_back(myHash);
        }
    }
    base_pow = 1;
    for(int i = 1; i < len; i++)
        base_pow *= base;
    unsigned int myHash = 0;
    for(int i = 0; i < len; i++)
        myHash = myHash * base + (s[i] - 'a');
    if(check(myHash))
        ans++;
    for(int i = len; i < s_len; i++)
    {
        myHash = myHash - base_pow * (s[i - len] - 'a');
        myHash = myHash * base + (s[i] - 'a');
        if(check(myHash))
            ans++;
    }
    fout << ans;
    return 0;
}