Cod sursa(job #2382300)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 18 martie 2019 08:48:22
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("abc2.in");
ofstream out("abc2.out");
const int MAX_LEN = 20000001,
          MOD = 1e9 + 9,
          EXP = 31;
bool E[MOD];
int preComp[21],
    wordSize, cnt;
string S, tmp;

int compHash(const string& s) {
    int hashVal = 0;

    for(int i = 0; i < s.size(); i++)
        hashVal = (1ULL * hashVal + 1ULL * (s[i] - 'a' + 1) * preComp[i]) % MOD;
    return hashVal;
}

void match() {
    for(int i = 0, j = S.size()-wordSize; i < j; i++)
        if(E[compHash(S.substr(i, wordSize))])
           cnt++;
}

int main()
{
    S.reserve(MAX_LEN);
    preComp[0] = 1;
    for(int i = 1; i <= 20; i++)
        preComp[i] = (1ULL * preComp[i-1] * EXP) % MOD;

    in >> S;
    in >> tmp;
    E[compHash(tmp)] = 1;
    wordSize = tmp.size();
    while(in >> tmp)
        E[compHash(tmp)] = 1;

    match();

    out << cnt << '\n';
    return 0;
}