Cod sursa(job #2100761)

Utilizator SenibelanMales Sebastian Senibelan Data 6 ianuarie 2018 12:27:05
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int TMAX = 10000005;
const int LMAX = 25;
const int MOD = 666013;
vector <uint32_t> Hash[MOD + 5];
char T[TMAX], cuv[LMAX];
int ltext, lcuv;
int sol;

bool Find(uint32_t hash){
    uint32_t List = hash % MOD;
    for(int i = 0; i < Hash[List].size(); ++i)
        if(Hash[List][i] == hash)
            return true;
    return false;
}

void Read(){
    in.getline(T, TMAX);
    ltext = strlen(T);
    while(in.getline(cuv, LMAX)){
        int l = strlen(cuv);
        uint32_t hash = 0;
        lcuv = l;
        for(int i = 0; i < l; ++i)
            hash = hash * 3 + (cuv[i] - 'a');
        if(!Find(hash))
            Hash[hash % MOD].push_back(hash);
    }
}

void SolveAndPrint(){
    uint32_t hash = 0, power = 1;
    for(int i = 0; i < lcuv; ++i){
        hash = hash * 3 + (T[i] - 'a');
        power *= 3;
    }
    power /= 3;
    sol += Find(hash);
    for(int i = lcuv; i < ltext; ++i){
        hash = (hash - power * (T[i - lcuv] - 'a')) * 3 + T[i] - 'a';
        sol += Find(hash); 
    }
    out << sol << "\n";
}

int main(){
    Read();
    SolveAndPrint();
    return 0;
}