Cod sursa(job #2106394)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 15 ianuarie 2018 18:40:12
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#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,put[22];
unordered_set<int>H;
unordered_set<int>::iterator it;
int hashh(char v[])
{
    int rez=0;
    for(int i=0;i<m;i++)
    {
        rez=((rez*26)+v[i]-'a'+1)%mod;
    }
    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<=21;i++)
    {
        put[i]=(1LL*put[i-1]*26)%mod;
    }
    H.insert(hashh(cuv));
    while(fin>>cuv)
    {
        H.insert(hashh(cuv));
    }
    int rez=hashh(sir);
    it=H.find(rez);
    if(it!=H.end()) nr++;
    for(i=1;i<n-m+1;i++)
    {
        rez=(mod+rez-((sir[i-1]-'a'+1)*put[m-1]))%mod;
        rez=((rez*26)+sir[i+m-1]-'a'+1)%mod;
        it=H.find(rez);
        if(it!=H.end()) nr++;
    }
    fout<<nr;
}