Cod sursa(job #2303794)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 16 decembrie 2018 21:42:11
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
#define mod 9973
using namespace std;
ifstream f ("abc2.in");
ofstream g ("abc2.out");
long long t,n,act,sol,t3,nr[50003],k;
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;
}
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)
        {
            ok=1;
            break;
        }
    }
    return ok;
}
void baga(long long cod)
{
    v[cod%mod].push_back(cod);
}
int main()
{
    ios::sync_with_stdio(false);
    f>>(s+1);
    n=strlen(s+1);
    f>>(p+1);
    t=strlen(p+1);
    nr[++k]=codific();
    while(f>>(p+1)) nr[++k]=codific();
    sort(nr+1,nr+k+1);
    for(int i=1;i<=k;++i) if(nr[i]!=nr[i-1]) baga(nr[i]);
    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;
}