Cod sursa(job #2108328)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 18 ianuarie 2018 03:31:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

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

const int N = 10000005;
const int MOD = 3420839;
char text[N];

struct hashul{
    long long val;
    hashul *next;
};

long long char2number[256];
hashul *(fcv[MOD]);

long long BIGGEST_POWER;
int WORD_LENGTH;

void init_char2number(){
    char2number['a'] = 1;
    char2number['b'] = 2;
    char2number['c'] = 3;
}

long long word2hash(char *s){
    if(!WORD_LENGTH)
    {
        WORD_LENGTH = strlen(s);
        BIGGEST_POWER = 1LL<<((WORD_LENGTH-1)*2);
    }

    long long crtPower = 1;
    long long hej = 0;
    for(int i=0; i<WORD_LENGTH; ++i)
    {
        hej += crtPower * char2number[s[i]];
        crtPower *= 4;
    }

    return hej;
}

int validateHash(long long hej){
    hashul *p = fcv[hej%MOD];
    while(p != NULL)
    {
        if(p->val == hej)
            return 1;
        p = p->next;
    }
    return 0;
}

int main()
{
    int sol = 0;
    char cuv[25];

    init_char2number();

    in.getline(text, N);
    ///cout<<text<<"\n";

    while(in.getline(cuv, 25))
    {
        ///cout<<cuv<<" "<<word2hash(cuv)<<"\n";
        hashul *crtHash = new hashul;
        crtHash->val = word2hash(cuv);
        crtHash->next = fcv[crtHash->val % MOD];
        fcv[crtHash->val % MOD] = crtHash;
    }


    long long crtHash = word2hash(text);
    ///cout<<"crtHash = "<<crtHash<<"\n";
    sol += validateHash(crtHash);
    for(int i=WORD_LENGTH; i < strlen(text); ++i)
    {
        crtHash = (crtHash / 4 + BIGGEST_POWER * char2number[text[i]]);
        ///for(int j=i - WORD_LENGTH + 1; j <= i; ++j) cout<<text[j]; cout<<" | crtHash = "<<crtHash<<"\n";
        sol += validateHash(crtHash);
    }

    ///cout<<"sol = "<<sol;
    out<<sol;


    return 0;
}