Cod sursa(job #2303808)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 16 decembrie 2018 22:05:34
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
#define mod 99969
using namespace std;
ifstream f ("abc2.in");
ofstream g ("abc2.out");
long long t,n,act,sol,t3;
char p[23],s[10000003];
vector <long long> v[mod+3];
long long codific()
{
    long long sol=0;
    for(int i=1;i<=t;++i)
    {
        sol=sol*3+(long long)(p[i]-'a');
    }
    return sol;
}
void baga()
{
    long long cod=codific();
    v[cod%mod].push_back(cod);
}
inline bool gasesc(long long x)
{
    long long cod=x%mod,ok=0;
    for(int i=0;i<v[cod].size();++i)
    {
        if(v[cod][i]==x)
        {
            swap(v[cod][i],v[cod][v[cod].size()-1]);
            //v[cod].pop_back();
            ok=1;
            break;
        }
    }
    return ok;
}
int main()
{
    ios::sync_with_stdio(false);
    f>>(s+1);
    n=strlen(s+1);
    f>>(p+1);
    t=strlen(p+1);
    baga();
    while(f>>(p+1)) baga();
    sol=0;
    for(int i=1;i<=t;++i)
    {
        act=act*3+(int)(s[i]-'a');
    }
    if(gasesc(act)) ++sol;
    t3=pow(3,t-1);
    for(int i=t+1;i<=n;++i)
    {
        act=(act-t3*(int)(s[i-t]-'a'))*3+(s[i]-'a');
        if(gasesc(act)) ++sol;
    }
    g<<sol;
    return 0;
}