Cod sursa(job #2295928)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 4 decembrie 2018 01:03:33
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <vector>
#include <string>
#include<math.h>
#define M 10041
#define N 10000050


using namespace std;

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

vector <unsigned int> hashtable[M];

int verify(unsigned int value)
{
    unsigned int indice=value%M;

    for(unsigned int i=0; i < hashtable[indice].size(); i++)
    {
        if(hashtable[indice][i] == value)
        {
            return 1;
        }
    }

    return 0;
}

unsigned int lsir,lcuvant;
unsigned int i ,j, sol,value,rollinghash;
string cuvant,sir;

int main()
{
    fin>>sir;
    fin>>cuvant;

    lcuvant=cuvant.size();
    value=0;
    for(i=0;i<=lcuvant-1;i++)
    {
        value = value*3+cuvant[i]-'a';
    }
    hashtable[value%M].push_back(value);


    while(fin>>cuvant)
    {
        value=0;
        for(i=0;i<=lcuvant-1;i++)
        {
            value=value*3+cuvant[i]-'a';
        }
        if(verify(value)==0)
        {
            hashtable[value%M].push_back(value);
        }
    }
    unsigned int power=1;
    for(i=1;i<=lcuvant-1;i++)
    {
        power=power*3;
    }
    rollinghash=0;

    for(i=0;i<=lcuvant-1;i++)
    {
        rollinghash=rollinghash*3+sir[i]-'a';
    }
    sol=0;
    sol=sol+verify(rollinghash);

    lsir=sir.size();
    for(i=lcuvant;i<=lsir-1;i++)
    {
        rollinghash=rollinghash-power*(sir[i - lcuvant]-'a');
        rollinghash=rollinghash*3+(sir[i]-'a');
        sol=sol+verify(rollinghash);
    }
    fout<<sol;
    fin.close();
    fout.close();
    return 0;
}