Cod sursa(job #2379934)

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

#define MOD 100021
#define PRIM 127
#define SZ 50021

using namespace std;

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

typedef unsigned int ui;

ui nr, szA, szB;
string A, B;
set < ui > hashTable[SZ];
ui hashed, P = 1, tempCalc;

int main()
{
    ui i, pos;

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

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

        for(i=0; i<szB; ++i)
            hashed = (((hashed << 7) - hashed) % MOD + B[i]) % MOD;

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

    hashed = 0;
    for(i=0; i<szB; ++i){
        hashed = (((hashed << 7) - hashed) % MOD + A[i]) % MOD;

        if(i!=0)
            P = ((P << 7) - P) % MOD;
    }

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

    for(i=szB; i<szA; ++i){
        tempCalc = (hashed - ((A[i - szB] * P) % MOD) + MOD);
        hashed = (((tempCalc << 7) - tempCalc) % MOD + A[i]) % MOD;

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

    g << nr;
    return 0;
}