Cod sursa(job #2038392)

Utilizator danstefanDamian Dan Stefan danstefan Data 13 octombrie 2017 17:32:19
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;
long long m,n,MOD=666013,lu,pu,i,cp,nr,j,ans,nrr;
char st[10000010],stt[40];
vector<int>h[666023];
long long caut(long long nr)
{
    nrr=nr%MOD;
    for(auto &it:h[nrr])
        if(it==nr)
        {
            return 1;
        }
    return 0;
}
int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    gets(st+1);
    lu=strlen(st+1);
    gets(stt+1);
    m=strlen(stt+1);
    pu=1;
    for(i=1; i<m; ++i)pu*=3;
    cp=pu;
    for(i=1; i<=m; ++i)
    {
        nr+=pu*(stt[i]-'a');
        pu/=3;
    }
    h[nr%MOD].push_back(nr);
    while(!feof(stdin))
    {
        gets(stt+1);
        nr=0;
        pu=cp;
        for(i=1; i<=m; ++i)
        {
            nr+=pu*(stt[i]-'a');
            pu/=3;
        }
        h[nr%MOD].push_back(nr);
    }
    nr=0;
    pu=cp;
    for(i=1; i<=m; ++i)
    {
        nr+=pu*(st[i]-'a');
        pu/=3;
    }
    ans=caut(nr);
    for(i=m+1; i<=lu; ++i)
    {
        nr-=cp*(st[i-m]-'a');
        nr*=3;
        nr+=(st[i]-'a');
        ans+=caut(nr);
    }
    printf("%lld\n",ans);
    return 0;
}