Cod sursa(job #2379897)

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

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

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;
vector < HASH > hashTable[SZ];
HASH hashed;
ull P1 = 1, P2 = 1, tempCalc1, tempCalc2;

string A, B;

bool searchHash(HASH &h)
{
    ui pos = (h.first + h.second) % SZ;
    ui sz  = hashTable[pos].size();

    for(ui i=0; i<sz; ++i)
        if(hashTable[pos][i].first == h.first && hashTable[pos][i].second == h.second)
            return true;
    return false;
}

int main()
{
    ui i;

    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;
        }

        if(!searchHash(hashed))
            hashTable[(hashed.first + hashed.second) % SZ].push_back(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;
        }
    }

    if(searchHash(hashed))
        ++nr;

    for(i=szB; i<szA; ++i){
        //hashB1 = ((PRIM1 * (hashB1 - ((B[i - szA] * P1) % MOD1) + MOD1)) % MOD1 + B[i]) % MOD1;
        //hashB2 = ((PRIM2 * (hashB2 - ((B[i - szA] * P2) % MOD2) + MOD2)) % MOD2 + B[i]) % MOD2;
        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;

        if(searchHash(hashed))
            ++nr;
    }

    g << nr;
    return 0;
}