Cod sursa(job #2379982)

Utilizator KemyKoTeo Virghi KemyKo Data 14 martie 2019 12:19:08
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <cstring>
#include <vector>

#define NMAX 10000001
#define PRIM 3
#define SZ 50021

using namespace std;

typedef unsigned int ui;

ui nr, szA, szB;
char A[NMAX], B[21];
vector < ui > hashTable[SZ];
ui hashed, P = 1, tempCalc;

bool searchHash(ui h)
{
    ui pos = h % SZ;
    ui sz  = hashTable[pos].size();

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

int main()
{
    ui i;

    freopen("abc2.in", "r", stdin);
    freopen("abc2.out","w", stdout);

    scanf("%s", A);
    szA = strlen(A);

    while(scanf("%s", B) != EOF){
        szB = strlen(B);
        hashed = 0;

        for(i=0; i<szB; ++i)
            hashed = (hashed << 1) + hashed + (B[i] - 'a');

        if(!searchHash(hashed))
            hashTable[hashed % SZ].push_back(hashed);
    }

    hashed = 0;
    for(i=0; i<szB; ++i){
        hashed = (hashed << 1) + hashed + (A[i] - 'a');

        if(i!=0)
            P = (P << 1) + P;
    }

    if(searchHash(hashed))
        ++nr;

    for(i=szB; i<szA; ++i){
        tempCalc = (hashed - ((A[i - szB] - 'a') * P));
        hashed   = (tempCalc << 1) + tempCalc + (A[i] - 'a');

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

    printf("%d\n", nr);
    return 0;
}