Cod sursa(job #2106402)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 15 ianuarie 2018 18:48:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <fstream>
#include <unordered_set>
#include <cstring>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char sir[10000010];
char cuv[22];
int m,mod=7013;
unsigned put[22];
unordered_set<unsigned int>H;
unordered_set<unsigned int>::iterator it;
unsigned int hashh(char v[])
{
    unsigned rez=0;
    for(int i=0;i<m;i++)
    {
        rez=((rez*3)+v[i]-'a');
    }
    return rez;
}
int main()
{
    fin>>sir;
    fin>>cuv;
    int n=strlen(sir),i,nr=0;
    m=strlen(cuv);
    put[0]=1;
    for(i=1;i<=20;i++)
    {
        put[i]=(1LL*put[i-1]*3)%mod;
    }
    H.insert(hashh(cuv));
    while(fin>>cuv)
    {
        H.insert(hashh(cuv));
    }
    unsigned int rez=hashh(sir);
    it=H.find(rez);
    if(it!=H.end()) nr++;
    for(i=1;i<n-m+1;i++)
    {
        rez=(rez-((sir[i-1]-'a')*put[m-1]));
        rez=((rez*3)+sir[i+m-1]-'a');
        it=H.find(rez);
        if(it!=H.end()) nr++;
    }
    fout<<nr;
}