Cod sursa(job #2303796)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 16 decembrie 2018 21:46:23
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define mod 9973
using namespace std;
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;
}
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]);
            ok=1;
            break;
        }
    }
    return ok;
}
void baga()
{
    long long cod=codific();
    if(gasesc(cod)) return;
    v[cod%mod].push_back(cod);
}
int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    scanf("%s",p+1);
    t=strlen(p+1);
    baga();
    while(scanf("%s",p+1)!=EOF) 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;
    }
    printf("%d\n",sol);
    return 0;
}