Cod sursa(job #2303806)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 16 decembrie 2018 22:02:58
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
#define mod 65536
using namespace std;
ifstream f ("abc2.in");
ofstream g ("abc2.out");
unsigned int t,n,act,sol,t3,nr[50003],k;
char p[23],s[10000003];
vector <unsigned int> v[mod+3];
unsigned int codific()
{
    unsigned int sol=0;
    for(int i=1;i<=t;++i)
    {
        sol=sol*3+(unsigned int)(p[i]-'a');
    }
    return sol;
}
inline bool gasesc(unsigned int x)
{
    unsigned int 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]);
            ok=1;
            break;
        }
    }
    return ok;
}
void baga(unsigned int 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);
    if(nr[1]==0) baga(0);
    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;
}