Cod sursa(job #2379975)

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

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

using namespace std;

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

typedef unsigned int ui;

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

int main()
{
    ui i, pos;

    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');

        pos = hashed % SZ;
        if(find(hashTable[pos].begin(), hashTable[pos].end(), hashed) == hashTable[pos].end())
            hashTable[pos].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;
    }

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

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

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

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