Cod sursa(job #2806912)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 23 noiembrie 2021 10:20:45
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <set>

using namespace std;

#pragma GCC optimize ("Ofast")

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

const int base = 3, mod = 50021;
int ans;
string s, cuv;
set <unsigned int> dictionar[mod + 2];
int len, s_len, base_pow = base;
unsigned int myHash;

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