Cod sursa(job #2379917)

Utilizator KemyKoTeo Virghi KemyKo Data 14 martie 2019 11:28:17
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <vector>
#include <set>
#include <string>

#define MOD1 4294959637
#define MOD2 4294967111
#define PRIM1 31
#define PRIM2 127
#define SZ 50021

using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ull, ull> HASH;

ui nr, szA, szB;
set < HASH > hashTable[SZ];
HASH hashed;
ull P1 = 1, P2 = 1, tempCalc1, tempCalc2;

string A, B;

int main()
{
    ui i, pos;

    f >> A;
    szA = A.size();

    while(f >> B){
        szB = B.size();
        hashed = {0, 0};

        for(i=0; i<szB; ++i){
            hashed.first  = (((hashed.first  << 5) - hashed.first)  % MOD1 + B[i]) % MOD1;
            hashed.second = (((hashed.second << 7) - hashed.second) % MOD2 + B[i]) % MOD2;
        }

        pos = (hashed.first + hashed.second) % SZ;
        if(hashTable[pos].find(hashed) == hashTable[pos].end())
            hashTable[pos].insert(hashed);
    }

    hashed = {0, 0};
    for(i=0; i<szB; ++i){
        hashed.first  = (((hashed.first  << 5) - hashed.first)  % MOD1 + A[i]) % MOD1;
        hashed.second = (((hashed.second << 7) - hashed.second) % MOD2 + A[i]) % MOD2;

        if(i!=0){
            P1 = ((P1 << 5) - P1) % MOD1;
            P2 = ((P2 << 7) - P2) % MOD2;
        }
    }

    pos = (hashed.first + hashed.second) % SZ;
    if(hashTable[pos].find(hashed) != hashTable[pos].end())
        ++nr;

    for(i=szB; i<szA; ++i){
        tempCalc1 = (hashed.first  - ((A[i - szB] * P1) % MOD1) + MOD1);
        tempCalc2 = (hashed.second - ((A[i - szB] * P2) % MOD2) + MOD2);

        hashed.first  = (((tempCalc1 << 5) - tempCalc1) % MOD1 + A[i]) % MOD1;
        hashed.second = (((tempCalc2 << 7) - tempCalc2) % MOD2 + A[i]) % MOD2;

        pos = (hashed.first + hashed.second) % SZ;
        if(hashTable[pos].find(hashed) != hashTable[pos].end())
            ++nr;
    }

    g << nr;
    return 0;
}