Cod sursa(job #2636309)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 17 iulie 2020 14:43:14
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
const int Mod = 666013;
vector <long long> h[Mod+5];
bool exista(long long val)
{
    int Key=val%Mod;
    for(auto it : h[Key])
    {
        if(it==val)
        {
            return true;
        }
    }
    return false;
}
void Add(long long val)
{
    if(exista(val))
    {
        return;
    }
    int Key=val%Mod;
    h[Key].push_back(val);
}
int main()
{
    string s,a;
    f>>s;
    int n=0;
    while(f>>a)
    {
        n=a.size();
        long long hes=0;
        for(auto it : a)
        {
            hes=1LL*hes*3+it-'a';
        }
        Add(hes);
    }
    long long hes=0,nr=0,put=1;
    for(int i=0;i<n;i++)
    {
        hes=1LL*hes*3+s[i]-'a';
        if(i>0)
        {
            put*=3;
        }
    }
    if(exista(hes))
    {
        ++nr;
    }
    for(int i=n;i<s.size();i++)
    {
        hes=1LL*(hes-1LL*put*(s[i-n]-'a'))*3+s[i]-'a';
        if(exista(hes))
        {
            ++nr;
        }
    }
    g<<nr<<'\n';
    return 0;
}