Cod sursa(job #2106412)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 15 ianuarie 2018 19:02:27
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char sir[10000010];
char cuv[22];
int m;
const int mod=7013;
unsigned put[22];
vector<unsigned int>H[mod];
vector<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;
}
void baga(unsigned int x)
{
    H[x%mod].push_back(x);
}
bool cauta(unsigned int x)
{
    int zum=x%mod;
    for(it=H[zum].begin();it!=H[zum].end();it++)
    {
        if(*it==x) return 1;
    }
    return 0;
}
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;
    }
    baga(hashh(cuv));
    while(fin>>cuv)
    {
        baga(hashh(cuv));
    }
    unsigned int rez=hashh(sir);
    if(cauta(rez)) nr++;
    for(i=m;i<n;i++)
    {
        rez=(rez-((sir[i-m]-'a')*put[m-1]));
        rez=((rez*3)+sir[i]-'a');
        if(cauta(rez)==1) nr++;
    }
    fout<<nr;
}